C#实现数独解法
作者:天方 时间:2022-10-25 18:22:43
数独简介
数独(shù dú)是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复 [1] 。
数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。
实现方式
今天晚上抽空把数独的计算机求解也给实现了一下,由于时间有限,我这里追求的是简洁而有效的解法,故用的是最原始而直观的回溯算法。速度也还可以接受,解网上最难的数独也大概就0.0X秒的样子。最开始是一个面向过程的实现,考虑到用的是C#的实现,便把这个算法给OO化了一下。
class Sudoku
{
public int[,] Numbers { get; set; }
int x;
int y;
public Sudoku(int[,] num)
{
Numbers = num;
for (x = 0; x < 9; x++)
{
for (y = 0; y < 9; y++)
{
if (Numbers[x, y] == 0)
return;
}
}
}
public bool IsCompleted { get { return x == 9 && y == 9; } }
//计算数独,返回null表示无法计算
public Sudoku CaluSudoKu()
{
if (IsCompleted)
return this;
foreach (var num in GetAvaibleNumbers())
{
var tmpData = Numbers.Clone() as int[,];
tmpData[x, y] = num;
var sudouku = new Sudoku(tmpData);
var ret = sudouku.CaluSudoKu();
if (ret != null)
return ret;
}
return null;
}
int[] GetAvaibleNumbers()
{
var set = new HashSet<int>(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
for (int i = 0; i < 9; i++)
{
set.Remove(Numbers[x, i]);
set.Remove(Numbers[i, y]);
}
int xStart = x - x % 3;
int yStart = y - y % 3;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
set.Remove(Numbers[i + xStart, j + yStart]);
}
}
return set.ToArray();
}
}
算法非常简单,大概就五六十行的样子,这种简单的算法自然谈不上高效,那些讨论数独算法的时间复杂度和空间复杂度的话题不在本文讨论范围之列。
来源:https://www.cnblogs.com/TianFang/archive/2008/12/18/1357840.html
标签:C#,实现,数独,解法
0
投稿
猜你喜欢
深入理解Java中的弱引用
2023-07-19 20:14:53
ios百度地图的使用(普通定位、反地理编码)
2023-07-03 15:26:17
浅谈C#中堆和栈的区别(附上图解)
2022-02-15 14:05:09
Java动态代理四种实现方式详解
2022-03-12 02:16:38
Android自定义渐变式炫酷ListView下拉刷新动画
2021-12-26 17:31:09
Gradle配置教程之自定义APK名称与输出路径
2023-03-04 17:35:27
Mybatis工具类JdbcTypeInterceptor运行时自动添加jdbcType属性
2023-08-24 03:49:59
SpringBoot整合Spring Data Elasticsearch的过程详解
2023-01-25 22:39:41
解析MapStruct转换javaBean时出现的诡异事件
2022-05-15 01:16:28
sweet alert dialog 在android studio应用问题说明详解
2022-12-14 04:17:53
java单机接口限流处理方案详解
2021-05-25 21:08:07
浅谈@FeignClient中name和value属性的区别
2023-11-06 13:04:14
C#获取字符串后几位数的方法
2022-06-07 21:39:33
SpringBoot实现模块日志入库的项目实践
2022-06-15 10:32:49
实例讲解Android中的AutoCompleteTextView自动补全组件
2022-05-10 15:35:10
Java包装类的概述与应用
2022-03-14 07:50:43
Spring boot 整合Logback过程示例解析
2021-12-06 04:05:52
flutter实现appbar下选项卡切换
2023-06-21 13:35:24
Unity创建平铺网格地图的方法
2022-07-06 16:05:49
vc提示unexpected end of file found的原因分析
2022-01-19 12:58:00