这么多年来，排队、无聊、打发时间的手机游戏就是 2048 和数独了。

既然还没有学会深度优先算法，不如先以人类解数度的方式，用代码来实现。

我回顾了一下代码，基本上看完任何一本入门书籍都看得懂。

数独

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


+-------+-------+-------+
| 4 2 · | · 5 · | 3 · 1 |
| 8 · 5 | 9 · · | · 4 · |
| · · · | · · · | 6 · · |
+-------+-------+-------+
| · 1 · | · 7 · | 2 · · |
| · · · | 2 · 5 | · · · |
| · · 7 | · 1 · | · 3 · |
+-------+-------+-------+
| · · 2 | · · · | · · · |
| · 9 · | · · 7 | 1 · 3 |
| 7 · 6 | · 8 · | · 2 9 |
+-------+-------+-------+

宫：每个 3x3 的小九宫格为一宫
行：…
列：…
数独规则：玩家需要根据 9×9 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、列、宫内的数字均含 1-9，不重复。
不可解：高级数独如「▻数独」的大师局，HoDoKu 的 Extreme 难度，到后期是无法用逻辑准确推演出下一个数字的，只能试错几个，需用试错的格子越多，则数独越难。
测试：
- 手机端用的 App Store 中的「▻数独来自 Finger Arts」大师局进行游玩
- PC 端用的 HoDoKu，方便来测试思路

思考 & 再思考

躺床上就一直在思考怎么把人类解数独的思路代入到代码里。。。

（排除法、扫看法，我自己按习惯命名的）

循环：找到几种 100% 能确定数字的方法，循环这些方法
- 排除法
- 扫看法
递归：在高级数独达到不可解状态时，用递归进行试错。可以直接用这个方法求出所有解，但如果发展的分支太多，会大大增加十到百倍的运行时间，所以先用循环中的方法先解出容易解的

思路：

1. 直接描绘出所有的潜在数字/候选数字（candidates）：

*. 每次填充数字，删除同宫、行、列的潜在数字

数独规则：同一个宫、行、列有且仅有一种数字，所以确定正确数字后，删除同宫、行、列的潜在数字，以供后面的方法进行准确寻找。

2. 排除法

第 3 行、第 6 列的格子，在其宫、行、列中已经有了「12345789」8 种数字，所以它必定是缺失的 6。

同样，6 一确定，第 3 行仅剩一个 9，所以必定是 9。

代码思路：这个格子只有一个候选数字，就是它了！

3. 扫看法

按人类逻辑可以很快用扫看法推算出下一个数字，用代码来实现这种思路感觉很麻烦，但是现在已经漏出一些端倪了。

代码思路：候选数字在当前宫唯一，则此格为此数。

*4. 剔除潜在数字

当宫内某一批候选数字形成一行或以列，则其他宫的此行此列的候选数字需要被剔除。

代码思路：遍历宫中个数 <= 3 的候选数字，如果它们在同一行、列，则删除其他宫中同一行、列的候选数字

转换成代码太麻烦了。。。跳过这一步吧，而且经过我的测试，高级数独补上这一步也是不可解状态

5. 循环

循环第 2 和第 3 步，我发现初级数独已经能全解了，高级数独还不行。

6. 试错，暴力递归

递归思路：

找到一个只有两种候选数字的格子，填入第一种
循环扫看法候补法进行新一轮的操作… … 循环停滞后检测合法性
- 不合法：返回上一层，填入另一个数字
- 合法：继续循环，循环不出新数字后再递归
  - 不合法：返回上一层，填入另一个数字
  - 合法：继续循环，循环不出新数字后再递归
    - 最后一次不合法：返回上一层，填入另一个数字
    - 最后一次合法：完成

即：一次深入的递归完成后，该格子可以确定或排除这个候选数字。

使用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


$ python suduku.py
请逐行输入数独内容，空白格用空格键代替，输入「A」初始化默认初级数独，输入「S」初始化默认最难数独，直接回车初始化默认高级数独
请输入第 1 行的内容：  17   29
请输入第 2 行的内容：78 2     
请输入第 3 行的内容：  9  18  
请输入第 4 行的内容： 1    6 2
请输入第 5 行的内容：   682   
请输入第 6 行的内容：9 6    7 
请输入第 7 行的内容：  34  5  
请输入第 8 行的内容：     3 96
请输入第 9 行的内容：17   62  

。。。

 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


*** 循环结束 共计填入过 87 次 ***                                       
+-------+-------+-------+
| · 6 · | 3 · · | · · 1 |
| 9 · · | · · 6 | 7 · · |
| 4 · 3 | · · · | · 2 · |
+-------+-------+-------+
| 5 · 9 | 8 · · | · · · |
| · · 4 | 5 · 7 | 3 · · |
| · · · | · · 3 | 6 · 8 |
+-------+-------+-------+
| · 4 · | · · · | 8 · 3 |
| · · 1 | 2 · · | · · 7 |
| 3 · · | · · 8 | · 4 · |
+-------+-------+-------+

+-------+-------+-------+
| 7 6 2 | 3 9 5 | 4 8 1 |
| 9 1 8 | 4 2 6 | 7 3 5 |
| 4 5 3 | 7 8 1 | 9 2 6 |
+-------+-------+-------+
| 5 3 9 | 8 6 2 | 1 7 4 |
| 6 8 4 | 5 1 7 | 3 9 2 |
| 1 2 7 | 9 4 3 | 6 5 8 |
+-------+-------+-------+
| 2 4 5 | 6 7 9 | 8 1 3 |
| 8 9 1 | 2 3 4 | 5 6 7 |
| 3 7 6 | 1 5 8 | 2 4 9 |
+-------+-------+-------+
数独已全解
共计用时 31.01515769958496 毫秒

代码思路

代码：https://github.com/iDvel/sudoku

数独二维数组样式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


[[{}, {}, {}, {}, {}, {}, {}, {}, {}],
 [{}, {}, {}, {}, {}, {}, {}, {}, {}],
 [{}, {}, {}, {}, {}, {}, {}, {}, {}],
 [{}, {}, {}, {}, {}, {}, {}, {}, {}],
 [{}, {}, {}, {}, {}, {}, {}, {}, {}],
 [{}, {}, {}, {}, {}, {}, {}, {}, {}],
 [{}, {}, {}, {}, {}, {}, {}, {}, {}],
 [{}, {}, {}, {}, {}, {}, {}, {}, {}],
 [{}, {}, {}, {}, {}, {}, {}, {}, {}]]
# 字典：
# num: 初始数字及后期已算出确定的数字，str
# can: candidates，候选数字，如果已确定数字则显示为[1]这种格式，方便调试，str
# box: 所在宫 row: 所在行 col: 所在列，int

让格子变成字典，方便寻找和调试。

填充候选数字：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


def fill_candidates(self):
    """填充所有候选数字"""
    for row in range(9):
        for col in range(9):
            unit = self.l[row][col]
            s = set()
            if unit['num'] is '·':
                s.update([u['num'] for u in self.get_list_of('box', unit['box'])])
                s.update([u['num'] for u in self.l[row]])
                s.update([u['num'] for u in self.get_list_of('col', unit['col'])])
                s.remove('·')
                s = {'1', '2', '3', '4', '5', '6', '7', '8', '9'} - s
                unit['can'] = ''.join(sorted(list(s)))
    self.show('can', '候选数字填写完毕')

这么搞主要是调试的时候方便我观察。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


*** 候选数字填写完毕 ***
+----------------------------+----------------------------+----------------------------+
|    278      [6]     2578   |    [3]    245789    2459   |    459      589      [1]   |
|    [9]     1258      258   |    14      12458     [6]   |    [7]      358      45    |
|    [4]     1578      [3]   |    179     15789     159   |    59       [2]      569   |
+----------------------------+----------------------------+----------------------------+
|    [5]     1237      [9]   |    [8]     1246      124   |    124      17       24    |
|   1268      128      [4]   |    [5]     1269      [7]   |    [3]      19       29    |
|    127      127      27    |    149     1249      [3]   |    [6]     1579      [8]   |
+----------------------------+----------------------------+----------------------------+
|    267      [4]     2567   |   1679     15679     159   |    [8]     1569      [3]   |
|    68       589      [1]   |    [2]     34569     459   |    59       569      [7]   |
|    [3]     2579     2567   |   1679     15679     [8]   |   1259      [4]     2569   |
+----------------------------+----------------------------+----------------------------+

排除法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def method_paichu(self):
    """排除：当前格只有一个候选数字，则此格为此数"""
    count = 0
    for row in range(9):
        for col in range(9):
            unit = self.l[row][col]
            if len(unit['can']) == 1:
                self.fill_number(unit, unit['can'])
                count += 1
                self.fill_count += 1
    self.method_count += 1
    self.show('can', desc='第 {} 次排除完毕，本次填充了 {} 个数字'.format(self.method_count, count))

扫看法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


def method_saokan(self):
    """扫看：候选数字在当前宫唯一，则此格为此数"""
    count = 0
    for box in self.get_list_of('boxes'):
        # 先得到只出现一次的数字
        l = []
        for unit in box:
            if '[' not in unit['can']:
                l.extend(unit['can'])
        # 存入列表，因为每个宫可能有不止一个
        only_one_list = [k for k, v in Counter(l).items() if v == 1]

        for unit in box:
            for the_one in only_one_list:
                if the_one in unit['can']:
                    # 填入数字，删除同行同列的相同候选数字
                    self.fill_number(unit, the_one)
                    count += 1
                    self.fill_count += 1

    self.method_count += 1
    self.show('can', '第 {} 次扫看完毕，本次填充了 {} 个数字'.format(self.method_count, count))

递归

写了个半吊子递归，等以后再优化一下吧。

总结

数独难度大致可分为 3 种：

简单，每个格子都能准确推演，运行时间 10ms 左右
高级，中后期只需试错几次，运行时间 30ms 左右
变态，从前期开始几乎每次都要试错，运行时间 3000ms 左右

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


变态版数独：
+-------+-------+-------+
| 8 · · | · · · | · · · |
| · · 3 | 6 · · | · · · |
| · 7 · | · 9 · | 2 · · |
+-------+-------+-------+
| · 5 · | · · 7 | · · · |
| · · · | · 4 5 | 7 · · |
| · · · | 1 · · | · 3 · |
+-------+-------+-------+
| · · 1 | · · · | · 6 8 |
| · · 8 | 5 · · | · 1 · |
| · 9 · | · · · | 4 · · |
+-------+-------+-------+

写完了发现挺乱的，数独其实用深度优先搜索算法最合适，写了一大堆有的没的，运行时间还比人家慢了 10 倍。。。主要是耗时在递归上了。

深度优先版运行变态版数独的时间大约在 300ms。

Python 数独

文章目录

数独