发布于 2020 年 11 月 09 日算法：简单数独的求解与生成
数独的规则
本文仅探讨经典数独的求解与生成。
数独的形式是下面这样的，一共有 81 个格子。
解数独时需要根据 9×9 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3×3）内的数字均含 1-9，不重复。
回溯算法
回溯法采用 试错 的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的 递归 方法来实现，在反复重复上述的步骤后可能出现两种情况：
找到一个可能存在的正确的答案
在尝试了所有可能的分步方法后宣告该问题没有答案
引用来源：回溯法 - 维基百科，自由的百科全书
数独的解法
数独的其中一个解法是回溯。
实现（TypeScript）
遍历所有格子，求出每一个空的格子可能填入的数值，这个数值是根据数独的规则得出的，可能有一个或多个。如果一个格子求不出可能的数值，则说明之前填入的数值有误，需要回溯，这个后面再说。
// 用来获得某个格子所在的九宫格中的其他数字
const getBox = (table: Array
const dx = Math.floor(x / 3)
const dy = Math.floor(y / 3)
const arr: Array
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
arr.push(table[i + dx * 3][j + dy * 3])
}
}
return arr
}
// 参数为一个格子所在行、列和九宫格中包含的数字
const getPossibleNumber = (
row: Array
col: Array
box: Array
) => {
// 数组中每个位置对应一个数字，位置上的数值代表数字出现的次数
const arr: Array
for (let i = 0; i < 9; i++) {
// 当数组元素不为空时，才会执行 && 后面的语句
row[i].trim() && arr[Number(row[i]) - 1]++
col[i].trim() && arr[Number(col[i]) - 1]++
box[i].trim() && arr[Number(box[i]) - 1]++
}
// 根据上面的结果，把数组转换成：仅包含出现次数为 0 的数字
// map 用来把出现次数为 0 的数字，转换为当前位置上的数字，其余的转换为 0
// filter 用来筛选非零元素，也就是之前的数组中出现次数为 0 的数字
return arr
.map((num, index) => (num === 0 ? index + 1 : 0))
.filter(num => !!num)
}
确定完可能的数值后，从中选一个数字，填入数独表，并假设填入的这个数字是好使的。
移动到下一个空格子，重复第一步，也就是重复求这个格子可能的数字，如果没有，就返回上一步，同时把上一步的操作还原，这个地方可以看下面的代码，利用了递归。
// 这个函数无返回值、不传 table 这个参数也可以用
const find = (table: Array
for (let i = x; i < 9; i++) {
// 这里是一个优化，让每一次递归都从上一次递归的那一行开始，减少了运算次数
let z = i === x ? y : 0
for (let j = z; j < 9; j++) {
// 仅当遇到空格子开始求解
if (table[i][j].trim() === '') {
const row = table[i] // 获取格子所在行的所有数字
const col = table.map(arr => arr[j]) // 获取各自所在列的所有数字
const box = getBox(table, i, j)
const result = getPossibleNumber(row, col, box)
// 根据可能填入数字的个数来判断下一步操作
switch (result.length) {
case 0: {
// 说明之前的格子填的不对，导致这个格子没有可以填的数字
return table
}
case 1: {
// 这个格子只有一个可能的数字
// 先把可能的数字填进去，假设是正确的，再去递归，查找下一个空格子
table[i][j] = result[0].toString()
table = find(table, i, j)
// ** 注意：这后面的代码都是递归完成之后执行的
// 判断一下最后一个格子，如果没有填，就恢复格子的状态，也就是设为空
// 否则就是数独已经全填满了，直接返回即可，不用恢复状态
if (table[8][8].trim() === '') {
table[i][j] = ' '
} else {
return table
}
return table
}
default: {
// 这个格子有多个可以填入的数字
// 和上一个一样，就是把填入一个数字，变成了循环列表，尝试填入列表中的每一个数字
for (let k = 0; k < result.length; k++) {
table[i][j] = result[k].toString()
table = find(table, i, j)
if (table[8][8].trim() === '') {
table[i][j] = ' '
} else {
return table
}
}
return table
}
}
}
}
}
return table
}
经过上面的步骤，如果数独有解，那么应该会填到最后一个格子，我们只要判断最后一个格子是否为空，就可以判断是否求解完成。
完整代码可以去 sudoku-solver/solve.ts at master · Lifeni/sudoku-solver 查看。
生成数独
原理
生成数独的算法与求解类似，需要随机生成一个棋盘，然后尝试求解，如果解不出来，就重新生成一个初始棋盘，也就是重复尝试，直到能得到一个完整的数独。
实现（C#）
随机生成一个初始棋盘，我这里采用的是随机生成对角线上的三个九宫格的方式，这三个九宫格中的数字互相之间不会受到数独规则的影响，所以只要随机生成 9 个数字，填入每个九宫格中就可以。相关代码和生成结果如下面所示：
do
{
InitSudoku();
for (int i = 0; i < 3; i++)
{
string[] temp = GetRandomArray();
int p = 0;
for (int j = 0 + (i * 3); j < 3 + (i * 3); j++)
{
for (int k = 0 + (i * 3); k < 3 + (i * 3); k++)
{
sudoku[j, k] = temp[p];
p++;
}
}
}
SolveSudoku();
// 当解出的数独没有填满时，说明数独无解，需要重新生成
} while (sudoku[8, 5] == " ");
# 生成结果示例
6,4,1, , , , , ,
7,5,3, , , , , ,
9,8,2, , , , , ,
, , ,9,3,7, , ,
, , ,4,6,5, , ,
, , ,1,8,2, , ,
, , , , , ,1,3,7
, , , , , ,8,2,9
, , , , , ,6,4,5
之后求解数独即可，如果求出的数独无解，就重复生成。这里不再重复贴上代码，有需要可以去 sudoku-generator/MainWindow.xaml.cs at master · Lifeni/sudoku-generator 看看。
经过上面的步骤，数独已经可以被求解出来，还需要进行挖空的操作。这个操作和生成数独也非常相似，先随机选一个格子设为空值，然后尝试求解，如果能求解就继续挖空，否则就还原挖空的操作。
int num = 40;
do
{
Random rx = new Random();
Random ry = new Random();
int x = rx.Next(0, 9);
int y = ry.Next(0, 9);
if (sudoku[x, y] != " ")
{
string[,] copy = new string[9, 9];
Array.Copy(sudoku, copy, sudoku.Length);
sudoku[x, y] = " ";
SolveSudoku();
// 检查数独是否已经填满
if (CheckResult())
{
copy[x, y] = " ";
num--;
}
Array.Copy(copy, sudoku, sudoku.Length);
}
} while (num > 0);
参考文章
JavaScript 九宫格数独生成算法_liusaint1992 的专栏-CSDN 博客