数独游戏的规则很简单，在9x9的矩阵中，每行、每列、每个九宫格中都需要填入1~9共九个数字，且不重复。
Peter Norvig 的这篇文章 Solving Every Sudoku Puzzle 详细介绍了一种解数独的方法。文中的代码基于 Python2 实现，我将其改写成了 JavaScript 的版本，项目可见 noiron/sudoku。
这篇文章中记录了我的理解而非原文的翻译，如果需要更详情的解释，可以查看原文。
数据的表示
首先需要考虑的是如何表示数据，数独的行使用 A-I 的字母表示，列使用 1-9 的数字表示。代码中用到了以下的术语/变量：
square所有81个格子的标记['A1', 'A2', 'A3', ... , 'I7', 'I8', 'I9']unit一个格子所在的行、列或九宫格unitList包含9行、9列、9个九宫格，共27个 unitpeers格子所在三个 unit 中的其他格子，共20个grid使用文本格式来表示数独的初始状态，1~9 代表数字，0或.代表此处未填入values一个以 square 为 key 的 map，给出每个格子的可能值，eg.{'A1':'12349', 'A2':'8', ...}
对于数独的初始状态使用文本格式来表示，如下所示的三种格式代表的是同一个数独：
1 | 4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4...... |
这部分的 JS 代码实现可以看代码：data.js
开始时，每个格子都可以是 1~9 的任何数字，然后从初始状态开始给每个格子填入相应的数字。解数独的过程就是在减少每个格子可以填入的数字，直到所有格子都能且只能填入1个数字。这里需要用到两种方法：约束传播（Constraint Propagation）和搜索（Search）。
约束传播（Constraint Propagation）
在处理数独的初始状态时用了 parseGrid() 函数，其中调用了
assign(values, square, digit) 方法，即将 digit 填入
square。
解数独有两个重要策略：
- 如果一个格子只有唯一的可选数字，则从它的 peers 中删除这个数字
- 如果一个 unit 中只有一个格子可以填入某一个数字，则将这个数字填入这个格子
这里需要使用 assign() 和 eliminate()
两个函数，代码见：solve.js
经过这个过程后一些简单的数独就可以得出解了，但对复杂的数独并非如此。所以需要使用搜索（Search） 来进一步处理。
搜索（Search）
这里的搜索指的是系统地尝试所有的可能性，直到找到解。对于数独来说就是对于每个未确定的格子，尝试填入一个可能的数字，然后继续搜索。如果出现了矛盾，就换一个数字。这是一个递归的过程，即深度优先搜索（depth-first search）。
search() 函数的具体代码见：solve.js
整体流程
整体的流程图如下：
flowchart TB
%% init(初始化)
开始 --> gridValues("gridValues()\n将字符串表示转换为map");
gridValues --> assign("assign()"\n给特定格子分配一个数字);
assign --> canAssign{分配过程\n没有矛盾?};
canAssign -- 无法分配 ----> 无解
canAssign -- 可以分配 --> eliminate("eliminate()\n进行约束传播");
eliminate --> onlyOne{发现某个格子只有\n唯一的可能性}
onlyOne -- 是的 --> assign
onlyOne -- 否 --> search("search()\n依次尝试可能的数字\nDFS递归处理");
search --> found{每个格子都能\n分配唯一的数字?}
found -- 不行 --> 无解 --> 结束
found -- 可以 --> 找到答案 --> 结束
至此就完成了数独的解法。
