吴锴的博客

Life? Don't talk to me about life!

0%

如何解数独

数独游戏的规则很简单,在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个 unit
  • peers 格子所在三个 unit 中的其他格子,共20个
  • grid 使用文本格式来表示数独的初始状态,1~9 代表数字,0或.代表此处未填入
  • values 一个以 square 为 key 的 map,给出每个格子的可能值,eg. {'A1':'12349', 'A2':'8', ...}

对于数独的初始状态使用文本格式来表示,如下所示的三种格式代表的是同一个数独:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......

400000805
030000000
000700000
020000060
000080400
000010000
000603070
500200000
104000000

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。

解数独有两个重要策略:

  1. 如果一个格子只有唯一的可选数字,则从它的 peers 中删除这个数字
  2. 如果一个 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 -- 可以 --> 找到答案 --> 结束
          

至此就完成了数独的解法。

欢迎关注我的其它发布渠道