数独求解程序

今晚上帮同学写了个求解数独的小程序,发出来记录下。

标准数独是9*9的,规则是行、列、每个小九宫都填入不重复的19,我们可以把这个经典游戏扩展到N阶,行和列的规则不变,可以加入对角线限制,即对角线也需要唯一的填入1N。对于N为完全平方的情况,可以加入分块,即类似经典数独那样,每一个小块也要唯一的填入1~N。

程序逻辑很简单,就是基本的回溯算法,和N皇后问题基本完全一样,下面给出求解程序的核心框架:

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
void Solve() {
int i = 0, j = -1;
if (!FindNextBlank(i, j))
return;

while (true) {
Number[i][j]++;
// Recall
if (Number[i][j] > order) {
// Clear this positon first
Number[i][j] = 0;
if (!FindPreviousBlank(i, j)) {
// Stop
return;
}
continue;
}

if (!CheckValid(i, j))
continue;

// Valid!!

// Found a solution
if (!FindNextBlank(i, j)) {
NofSolutions++;
if (printSolution) {
PrintSudoku();
}

// Find next solution
i = order - 1, j = order;
FindPreviousBlank(i, j);
}
// else find next blank positon
}
}

CheckValid()是与规则有关的判断填入数字合法性的函数,FindNextBlank()FindPreviousBlank()两个函数用于寻找下一个及上一个空位置,参数使用引用的方式传递,返回结果直接修改了传入值。

程序中先从第一个空位置开始,依次尝试所有取值,找到一个合法值后,开始填下一个空位置;若达到最后一个空位置,则说明找到了一个解,输出后继续循环;若当前位置尝试完所有取值后,依然没有合法值,说明之前填的有误,需要回溯,清除当前位置的值后会退到上一个空位置继续循环即可。

完整的程序代码见GitHub


参考资料:
SudokuPuzzle
总共有多少个数独?