大多数都有注释，配合注释应该不难理解，如有问题欢迎评论区交流。稍微说一下，重载ToString是为了方便调试和查看状态，其中空心方框表示未填写数字的单元格，数字表示题目给出数字的单元格，圈数字表示唯一数单元格填写的数字，括号数字表示有多个候选数通过尝试（暴力搜索）确定的数字。注意类文件最上面有一个using static System.Math; 导入静态类，不然每次调用数学函数都要 Math. ，很烦。
求解过程信息
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
public class PathTree { public PathTree Parent { get; set; } public List<PathTree> Children { get; } = new List<PathTree>(); public SudokuBlock Block { get; } public int X { get; } public int Y { get; } public int Number { get; } public bool Pass { get; private set; } = true; public (byte x, byte y)[] SetList { get; set; } public PathTree(SudokuBlock block, int x, int y, int number) { Block = block; X = x; Y = y; Number = number; } public PathTree(SudokuBlock block, int row, int column, int number, PathTree parent) : this(block, row, column, number) { Parent = parent; Parent.Children.Add(this); } public void SetPass(bool pass) { Pass = pass; } } |
其中记录了每个步骤在哪个单元格填写了哪个数字，上一步是哪一步，之后尝试过哪些步骤，这一步是否会导致之后的步骤出现死路，填写数字后影响到的单元格和候选数字（用来在悔步的时候恢复相应单元格的候选数字）。
答案存储
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
public class SudokuState { public SudokuBlock[][] SudokuBoard { get; } public SudokuState(SudokuSolver sudoku) { SudokuBoard = new SudokuBlock[sudoku.SudokuBoard.Length][]; //初始化数独的行 for (int i = 0; i < sudoku.SudokuBoard.Length; i++) { SudokuBoard[i] = new SudokuBlock[sudoku.SudokuBoard[i].Length]; //初始化每行的列 for (int j = 0; j < sudoku.SudokuBoard[i].Length; j++) { SudokuBoard[i][j] = new SudokuBlock( sudoku.SudokuBoard[i][j].IsCondition , null , sudoku.SudokuBoard[i][j].Number , (byte)i , (byte)j); if (sudoku.SudokuBoard[i][j].IsUnique) { SudokuBoard[i][j].SetUnique(); } } } } public override string ToString() { static string Str(SudokuBlock b) { var n1 = new[] { "①", "②", "③", "④", "⑤", "⑥", "⑦", "⑧", "⑨" }; var n2 = new[] { "⑴", "⑵", "⑶", "⑷", "⑸", "⑹", "⑺", "⑻", "⑼" }; return b.Number.HasValue ? b.IsCondition ? " " + b.Number : b.IsUnique ? n1[b.Number.Value - 1] : n2[b.Number.Value - 1] : "▢"; } return$@"{Str(SudokuBoard[0][0])},{Str(SudokuBoard[0][1])},{Str(SudokuBoard[0][2])},{Str(SudokuBoard[0][3])},{Str(SudokuBoard[0][4])},{Str(SudokuBoard[0][5])},{Str(SudokuBoard[0][6])},{Str(SudokuBoard[0][7])},{Str(SudokuBoard[0][8])}{Str(SudokuBoard[1][0])},{Str(SudokuBoard[1][1])},{Str(SudokuBoard[1][2])},{Str(SudokuBoard[1][3])},{Str(SudokuBoard[1][4])},{Str(SudokuBoard[1][5])},{Str(SudokuBoard[1][6])},{Str(SudokuBoard[1][7])},{Str(SudokuBoard[1][8])}{Str(SudokuBoard[2][0])},{Str(SudokuBoard[2][1])},{Str(SudokuBoard[2][2])},{Str(SudokuBoard[2][3])},{Str(SudokuBoard[2][4])},{Str(SudokuBoard[2][5])},{Str(SudokuBoard[2][6])},{Str(SudokuBoard[2][7])},{Str(SudokuBoard[2][8])}{Str(SudokuBoard[3][0])},{Str(SudokuBoard[3][1])},{Str(SudokuBoard[3][2])},{Str(SudokuBoard[3][3])},{Str(SudokuBoard[3][4])},{Str(SudokuBoard[3][5])},{Str(SudokuBoard[3][6])},{Str(SudokuBoard[3][7])},{Str(SudokuBoard[3][8])}{Str(SudokuBoard[4][0])},{Str(SudokuBoard[4][1])},{Str(SudokuBoard[4][2])},{Str(SudokuBoard[4][3])},{Str(SudokuBoard[4][4])},{Str(SudokuBoard[4][5])},{Str(SudokuBoard[4][6])},{Str(SudokuBoard[4][7])},{Str(SudokuBoard[4][8])}{Str(SudokuBoard[5][0])},{Str(SudokuBoard[5][1])},{Str(SudokuBoard[5][2])},{Str(SudokuBoard[5][3])},{Str(SudokuBoard[5][4])},{Str(SudokuBoard[5][5])},{Str(SudokuBoard[5][6])},{Str(SudokuBoard[5][7])},{Str(SudokuBoard[5][8])}{Str(SudokuBoard[6][0])},{Str(SudokuBoard[6][1])},{Str(SudokuBoard[6][2])},{Str(SudokuBoard[6][3])},{Str(SudokuBoard[6][4])},{Str(SudokuBoard[6][5])},{Str(SudokuBoard[6][6])},{Str(SudokuBoard[6][7])},{Str(SudokuBoard[6][8])}{Str(SudokuBoard[7][0])},{Str(SudokuBoard[7][1])},{Str(SudokuBoard[7][2])},{Str(SudokuBoard[7][3])},{Str(SudokuBoard[7][4])},{Str(SudokuBoard[7][5])},{Str(SudokuBoard[7][6])},{Str(SudokuBoard[7][7])},{Str(SudokuBoard[7][8])}{Str(SudokuBoard[8][0])},{Str(SudokuBoard[8][1])},{Str(SudokuBoard[8][2])},{Str(SudokuBoard[8][3])},{Str(SudokuBoard[8][4])},{Str(SudokuBoard[8][5])},{Str(SudokuBoard[8][6])},{Str(SudokuBoard[8][7])},{Str(SudokuBoard[8][8])}"; } } |
没什么好说的，就是保存答案的，因为有些数独的解不唯一，将来有机会扩展求多解时避免相互覆盖。
还有一个辅助类，单元格定义
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
public class SudokuBlock{ /// <summary> /// 填入的数字 /// </summary> public byte? Number { get; private set; } /// <summary> /// X坐标 /// </summary> public byte X { get; } /// <summary> /// Y坐标 /// </summary> public byte Y { get; } /// <summary> /// 候选数字，下标所示状态表示数字“下标加1”是否能填入 /// </summary> public BitArray Candidate { get; private set; } /// <summary> /// 是否为条件（题目）给出数字的单元格 /// </summary> public bool IsCondition { get; } /// <summary> /// 是否为游戏开始就能确定唯一可填数字的单元格 /// </summary> public bool IsUnique { get; private set; } public SudokuBlock(bool isCondition, BitArray candidate, byte? number, byte x, byte y) { IsCondition = isCondition; Candidate = candidate; Number = number; IsUnique = false; X = x; Y = y; } public void SetNumber(byte? number) { Number = number; } public void SetCandidate(BitArray candidate) { Candidate = candidate; } public void SetUnique() { IsUnique = true; }} |
测试代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
static void Main(string[] args) { //模板 //byte[][] game = new byte[][] { // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0}, // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0}, // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0}, // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0}, // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0}, // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0}, // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0}, // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0}, // new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},}; //这个简单，无需尝试，一直填唯一数单元格，填完后剩下的单元格又有会变唯一数单元格 //byte[][] game = new byte[][] { // new byte[]{0, 5, 0, 7, 0, 6, 0, 1, 0}, // new byte[]{0, 8, 0, 0, 9, 0, 0, 6, 0}, // new byte[]{0, 6, 9, 0, 8, 0, 7, 3, 0}, // new byte[]{0, 1, 0, 0, 4, 0, 0, 0, 6}, // new byte[]{6, 0, 7, 1, 0, 3, 8, 0, 5}, // new byte[]{9, 0, 0, 0, 0, 8, 0, 2, 0}, // new byte[]{0, 2, 4, 0, 1, 0, 6, 5, 0}, // new byte[]{0, 7, 0, 0, 6, 0, 0, 4, 0}, // new byte[]{0, 9, 0, 4, 0, 2, 0, 8, 0},}; //可以填一部分唯一数单元格，剩下一部分需要尝试，调试用 //byte[][] game = new byte[][] { // new byte[]{7, 0, 0, 5, 0, 0, 0, 0, 2}, // new byte[]{0, 3, 0, 0, 0, 4, 6, 0, 0}, // new byte[]{0, 0, 2, 6, 0, 0, 0, 0, 0}, // new byte[]{2, 0, 0, 0, 7, 0, 0, 0, 5}, // new byte[]{5, 0, 0, 1, 0, 3, 0, 0, 6}, // new byte[]{3, 0, 0, 4, 0, 0, 0, 0, 9}, // new byte[]{0, 0, 0, 0, 0, 1, 5, 0, 0}, // new byte[]{0, 0, 7, 2, 0, 0, 0, 4, 0}, // new byte[]{4, 0, 0, 0, 0, 9, 0, 0, 7},}; //全部要靠尝试来填 byte[][] game = new byte[][] { new byte[]{1, 0, 0, 2, 0, 0, 3, 0, 0}, new byte[]{0, 4, 0, 5, 0, 0, 0, 6, 0}, new byte[]{0, 0, 0, 7, 0, 0, 8, 0, 0}, new byte[]{3, 0, 0, 0, 0, 7, 0, 0, 0}, new byte[]{0, 9, 0, 0, 0, 0, 0, 5, 0}, new byte[]{0, 0, 0, 6, 0, 0, 0, 0, 7}, new byte[]{0, 0, 2, 0, 0, 4, 0, 0, 0}, new byte[]{0, 5, 0, 0, 0, 6, 0, 9, 0}, new byte[]{0, 0, 8, 0, 0, 1, 0, 0, 3},}; var su = new SudokuSolver(game); var r = su.Solve(); var r1 = r.First(); static IEnumerable<PathTree> GetPath(PathTree pathTree) { List<PathTree> list = new List<PathTree>(); var path = pathTree; while (path.Parent != null) { list.Add(path); path = path.Parent; } return list.Reverse<PathTree>(); } var p = GetPath(r1.path).Select(x => $"在 {x.X + 1} 行 {x.Y + 1} 列填入 {x.Number}"); foreach(var step in p) { Console.WriteLine(step); } Console.WriteLine(r1.sudoku); Console.ReadKey(); } |
结果预览：
上面还有，更多步骤，太长，就不全部截下来了。关于第二张图详情请看后面的总结部分。
总结
这个数独求解器运用了大量 C# 7 的新特性，特别是 本地函数 和 基于 Tulpe 的简写的多返回值函数，能把本来一团乱的代码理清楚，写清爽。 C# 果然是比 Java 这个躺在功劳簿上吃老本不求上进的坑爹语言爽多了。yield return 返回迭代器这种简直是神仙设计，随时想返回就返回，下次进来还能接着上次的地方继续跑，写这种代码简直爽翻。另外目前多解求解功能还不可用，只是预留了集合返回类型和相关参数，以后看情况吧。
如果你看过我的这篇文章.Net Core 3 骚操作 之 用 Windows 桌面应用开发 Asp.Net Core 网站，你也可以在发布启动网站后访问https://localhost/Sudoku来运行数独求解器，注意，调试状态下端口为5001。
本文地址：https://www.cnblogs.com/coredx/p/12173702.html
完整源代码：Github
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。
