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

Python 初级水平,我回顾了一下代码,基本上看完任何一本入门书籍都看得懂。

数独

 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,等我学了相关算法再来优化吧。。。