温州五旬老伯自制纸板 破解史上最难数独游戏
08:26:00&&来源：《钱江晚报》
[提要]&&“芬兰数学家因卡拉花费3个月设计出了世界上迄今难度最大的数独游戏。之前有消息称这道题是“世界最难”，林敏舫说，她也就此查阅过芬兰数学家因卡拉就这道题目接受采访时的资料。
　　“芬兰数学家因卡拉花费3个月设计出了世界上迄今难度最大的数独游戏。”今年6月30日，英国《每日邮报》的一篇报道，被国内媒体转载后，引起了张亦桃的兴趣。
　　“这题既然有答案，解出来只是时间问题。”家住温州的张亦桃，今年56岁，很喜欢玩这类逻辑游戏，这道难题一下子挑起了他的斗志。
　　结果，他说自己花了5个小时，就成功破解了这个数独。
　　张老伯果真攻克了数独界最难吗？
　　雕刻师傅喜欢玩逻辑游戏
　　数独流行有一阵子了，简单来说，就是一种逻辑游戏：
　　玩家需要根据9×9格子内的已知数字，推理出剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3×3）内的数字，均含1到9，且不重复。
　　7月13日，张亦桃无意间看到了因卡拉设计的这道数独难题，顿时来了兴趣。
　　张亦桃说，他小时候常和伙伴们玩九宫格等游戏，那时好胜心就比较强，也渐渐喜欢上了这类考逻辑的东西。
　　初中辍学后，他去学了雕刻手艺，工作比较忙，也就没怎么玩过了。
　　上了年纪后，闲下来的张亦桃又玩起了一些逻辑游戏。
　　比如，前段时间他就在琢磨这样一道题：
　　在19×19盘面上，填入361个不同数字，使每行、每列及两条对角线的和，各等于3439，这1到361个数字，具体怎么填？
　　“后来我发现了规律，觉得很有意思。”张亦桃说。
　　老伯自制60块纸板“摆出”了答案
　　再说那道号称“世界最难”数独题。张亦桃拿到题后，坐在那里考虑了半天，一时找不到什么演算好办法。
　　为了让自己思路清晰点，他立即动手做了一套工具――81个格子中，21格已经给出数字，剪出60块纸板，写上余下的数字，再把表格放大，像摆阵型一般，一个个排除演算。
　　张亦桃说，这套工具也只是辅助，也就比铅笔写了再擦掉，要清楚一些，具体推算起来，还是很麻烦的，“有时这里一个数字填错了，那边的也要改，搞不好脑子就乱掉了。”
　　一开始，他花了两个小时，排出了一个结果，“我以为破解了，后来一看，并没有满足全部要求。”
　　推倒重来，张亦桃憋了口气，“我信心一直很足的，这题既然有答案，解出来只是时间问题。”
　　他又摆了近3个小时，终于“摆出”了这道数独题。
　　“后来觉得，没有想象中那么难。”张亦桃笑着说。
　　专业选手说，敬佩老伯的精神
　　这道神奇的数独题，一直被传说是最难的，那么它究竟是不是呢？
　　昨日（7月20日），记者联系上了杭州姑娘林敏舫。她从2005年12月开始钻研“数独”，是年世界数独锦标赛，2011年世界谜题锦标赛中国队队员。
　　林敏舫告诉记者，这道题在网上很火，她也注意到了。
　　她确认这一道题确实只有唯一解，不过是一道非逻辑解的题目。“因此我就没有刻意去解答。因为对于喜欢做数独题的人来说，用逻辑推理解答的过程才是享受。”
　　林敏舫的数独圈子里，有位好友是成都电子科技大学的学生，叫王嘉豪。王嘉豪拿到这道题后，花了半小时解出答案。
　　林敏舫说，这道题算是一道很难的数独题，但并非最难的，她和朋友们都做到过更难的题。
　　温州张大伯解出这道题的事情，林敏舫也听说了。她在微博上表示，十分敬佩老伯的精神。
　　林敏舫说，老人所用的方法是最原始的办法“枚举”，例举各种可能性，逐一排除，通俗地说就是“试数”。运气好的话，就能快一点解答出题目。
　　之前有消息称这道题是“世界最难”，林敏舫说，她也就此查阅过芬兰数学家因卡拉就这道题目接受采访时的资料。
　　林敏舫说，因卡拉并没有在采访中很强硬地表示这道题就是最难的数独题。而且林敏舫认为，在数独圈子里，谁都知道只有更难，没有最难。“我想，一位有名的数学家，也不会做出那么绝对的表述。”（戚祥浩、解亮、张琴）
来源：《钱江晚报》(如何)解决任意的数独谜题 - 技术翻译 - 开源中国社区
(如何)解决任意的数独谜题
【已翻译100%】
英文原文：
推荐于 4年前 (共 20 段, 翻译完成于 09-26)
参与翻译&(7人)&: ,
本文中我将解决任意的数独谜题的求解问题。利用两个想法:&和，求解将是很容易（大约一页的代码完成主要想法，两页代码完成其他的辅助功能）能够实现的。
数独符号和初步概念
首先，我们要对一些标记符号有共识。数独谜题是一个9*9的表格，大多数数独爱好者把列标记为1-9，把行标记为A-I，并且称每9个小方格（一行，一列，或者3*3的格子）组成的一个局部区域为一个单元(unit)，共享同一个unit的小方格称为节点(peer)。游戏中，有的小方格留空，其他的填上一些数字，问题是：
若每个unit中的数字都是一个1-9的排列，则问题得到解决。
也就是说，每个unit中的数字都只能出现一次，不能出现两次。这等价于每个方格的数字都和它的peer的数字不同。下面是每一个小方格的名字，一个典型的数独问题，以及问题的解。
A1 A2 A3| A4 A5 A6| A7 A8 A9
4 . . |. . . |8 . 5
4 1 7 |3 6 9 |8 2 5
B1 B2 B3| B4 B5 B6| B7 B8 B9
. 3 . |. . . |. . .
6 3 2 |1 5 8 |9 4 7
C1 C2 C3| C4 C5 C6| C7 C8 C9
. . . |7 . . |. . .
9 5 8 |7 2 4 |3 1 6
---------+---------+---------
------+------+------
------+------+------
D1 D2 D3| D4 D5 D6| D7 D8 D9
. 2 . |. . . |. 6 .
8 2 5 |4 3 7 |1 6 9
E1 E2 E3| E4 E5 E6| E7 E8 E9
. . . |. 8 . |4 . .
7 9 1 |5 8 6 |4 3 2
F1 F2 F3| F4 F5 F6| F7 F8 F9
. . . |. 1 . |. . .
3 4 6 |9 1 2 |7 5 8
---------+---------+---------
------+------+------
------+------+------
G1 G2 G3| G4 G5 G6| G7 G8 G9
. . . |6 . 3 |. 7 .
2 8 9 |6 4 3 |5 7 1
H1 H2 H3| H4 H5 H6| H7 H8 H9
5 . . |2 . . |. . .
5 7 3 |2 9 1 |6 8 4
I1 I2 I3| I4 I5 I6| I7 I8 I9
1 . 4 |. . . |. . .
1 6 4 |8 7 5 |2 9 3
每一个小方格都有三个unit，并且拥有20个peer，下面就是C2的节点的units和peers:
C1 C2 C3| C4 C5 C6| C7 C8 C9
---------+---------+---------
---------+---------+---------
---------+---------+---------
---------+---------+---------
---------+---------+---------
---------+---------+---------
我们可以用Python实现units，peers，以及小方格的标记，如下所示：
def cross(A, B):
"Cross product of elements in A and elements in B."
return [a+b for a in A for b in B]
= 'ABCDEFGHI'
= cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
[cross(r, cols) for r in rows] +
[cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units = dict((s, [u for u in unitlist if s in u]) for s in squares)
peers = dict((s, set(sum(units[s],[]))-set([s])) for s in squares)
&翻译得不错哦！
如果你不熟悉Python的一些特性的话，记住字典是Python中哈希表的名字，用来映射键-值对；键-值对是用(键, 值)元组表示；dict((s, [...]) for s in squares)创建一个字典，其中每个小方格对应list[...]中的一个值；表达式[u for u in unitlist if s in u]的意思是如果小方块s是u的一个成员，那么结果是units u的列表。所以这条赋值语句可以理解为“units是一个字典，将各个小方块映射到包含小方块的units的一个列表”。下一条赋值语句可以相似的理解为“peers是一个字典，将各个小方块映射到由units中的小方块联合组成的集合，其中不包括小方块自身。”
用几个测试试试看（它们都通过了）：
def test():
"A set of unit tests."
assert len(squares) == 81
assert len(unitlist) == 27
assert all(len(units[s]) == 3 for s in squares)
assert all(len(peers[s]) == 20 for s in squares)
assert units['C2'] == [['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'],
['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'],
['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]
assert peers['C2'] == set(['A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2',
'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9',
'A1', 'A3', 'B1', 'B3'])
print 'All tests pass.'
&翻译得不错哦！
既然我们有了方块(squares)、单位(units)和节点(peers)，下一步就是定义玩数独的网格。实际上我们需要两个表示：第一，用来指定数独谜题初始状态的文本格式；我们将使用grid命名。第二，用来表示数独谜题的任何内部状态，部分解决或者全部解决；我们把它叫做values集合，因为它将给出各个方块内的所有剩余的可能值。对于文本格式（grid），我们允许用1-9中的字符表示数字，0或者句号表示一个空方块。其它字符被忽略（包括空格、换行、破折号和竖线）。所以，下面三个grid字符串表示的是同一个数独谜题：
"4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......"
4 . . |. . . |8 . 5
. 3 . |. . . |. . .
. . . |7 . . |. . .
------+------+------
. 2 . |. . . |. 6 .
. . . |. 8 . |4 . .
. . . |. 1 . |. . .
------+------+------
. . . |6 . 3 |. 7 .
5 . . |2 . . |. . .
1 . 4 |. . . |. . .
&翻译得不错哦！
现在处理值。也许有人觉得9 x 9阵列是很显然的数据结构。但方块的名字是类似‘A1’的形式，不是（0,0）。因此，值将是个以方块为键的字典。每个键的值是其所在方块中的可能数字：可能是数独谜题已给定部分的一个单独的数字，或者是我们算出它一定是某个数字，也可以是我们暂时不确定的一些数的集合。数字集合可以用Python中的set或者list表示，但我选择使用数字字符串（一会我们将看到原因）。这样，A1是7、C7为空的网格可以表示为{'A1':'7'，'C7':'',...}。
下面是把一个网格表示为值的字典的代码：
def parse_grid(grid):
"""Convert grid to a dict of possible values, {square: digits}, or
return False if a contradiction is detected."""
## To start, every squ then assign values from the grid.
values = dict((s, digits) for s in squares)
for s,d in grid_values(grid).items():
if d in digits and not assign(values, s, d):
return False ## (Fail if we can't assign d to square s.)
return values
def grid_values(grid):
"Convert grid into a dict of {square: char} with '0' or '.' for empties."
chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
return dict(zip(squares, chars))
&翻译得不错哦！
parse_grid函数中会调用assign(values, s, d)。我们可以仅仅做到values[s] = d，但显然可以做得更多。有经验的读者应当清楚以下两条重要的策略：
(1) 如果一个空格仅有一个可能的值，则与该空格相关的（同行、同列、同一个３*３的区域）空格就不可能取这个值； (2) 如果一个区域（同行、同列、同一个３*３区域）仅有一个空格能够填入值x，则该空格应该填入这个值x。
举例来说：
(1) 若我们在A1中填入7，{'A1': 7, 'A2': '', ...}，此时，7可以从A1的相关格子A2的列表中移除，即{'A1': 7, 'A2': '', ...}。
(2) 若从A3至A9没有一个空格能够填入3，那么3必定填在2中，即 {'A1': 7, 'A2': 3, ...}
当A2被填入３之后，继而会影响与A2相关的格子的约束，与更新约束相关的格子就可能找到正确的答案，以此类推，这种传递的过程称为约束传递。
函数 assign(values, s, d)　将返回被更新后的所有81个格子的值，但如果其中发生冲突，就将返回False. 例如，如果A1中填入了７，而最后传递的结果将在A２中填入７，这种情况显然不符合数独的规则。
&翻译得不错哦！
因此，最基本的操作并不是填入一个数字，而是迭代地淘汰掉每个格子不可能的数字，具体实际参见 eliminate(values, s, d)。在有了eliminate函数之后，assign函数就更容易地定义为，对于某一格子，去除所有不可能的数字，而留下数字d。
def assign(values, s, d):
"""去除所有在values[s]中不可能的数字，除了数字d，继而进行约束传递
Return values, 若return False表示发生冲突。"""
other_values = values[s].replace(d, '')
if all(eliminate(values, s, d2) for d2 in other_values):
return values
return False
def eliminate(values, s, d):
"""从values[s]中去除d，继而进行约束传递。
Return values, 若return False表示发生冲突。"""
if d not in values[s]:
return values ## d表不在values[s]中
values[s] = values[s].replace(d,'')
## (1) 如果一个格子中只有一个值d2，则将d2从其相关的格子中去除。（同行、同列、同3*3区域）
if len(values[s]) == 0:
return False ## 矛盾
elif len(values[s]) == 1:
d2 = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
## (2) 如果同行、同列、同３*３区域中发现只有一个格子填入d，则将d放在该格子中
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False ## 矛盾，没有格子可以填入
elif len(dplaces) == 1:
# d只能填入一个格子
if not assign(values, dplaces[0], d):
return False
return values
接下来，我们更近一步，来将一个数独游戏显示出来：
def display(values):
"2-D的显示数独的结果"
width = 1+max(len(values[s]) for s in squares)
line = '+'.join(['-'*(width*3)]*3)
for r in rows:
print ''.join(values[r+c].center(width)+('|' if c in '36' else '')
for c in cols)
if r in 'CF': print line
到这里，我想我们可以试一下了！我从&上选择了简单任务中的第一个列子：
&&& grid1 = ''
&&& display(parse_grid(grid1))
4 8 3 |9 2 1 |6 5 7
9 6 7 |3 4 5 |8 2 1
2 5 1 |8 7 6 |4 9 3
------+------+------
5 4 8 |1 3 2 |9 7 6
7 2 9 |5 6 4 |1 3 8
1 3 6 |7 9 8 |2 4 5
------+------+------
3 7 2 |6 8 9 |5 1 4
8 1 4 |2 5 3 |7 6 9
6 9 5 |4 1 7 |3 8 2
对于这个样例，完全可以用第(1)与(2)个策略解决！但不幸的是，并不是所有的数独都如此的简单，如困难任务中的第一个样例：
&&& grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
&&& display(parse_grid(grid2))
1256789 | 14589
245689 | 12679
5689 | 12369
------------------------+------------------------+------------------------
------------------------+------------------------+------------------------
&翻译得不错哦！
这种情况下，我们仍然没有解决上述数独问题，因为还有61个位置没有填写数字。接下来要怎样做呢？也许我们应该编写一些更复杂的策略，例如naked twins策略，该策略查找同一个单元的两个不同位置(这两个位置要有着相同的待填写数字)，如{'A5': '26', 'A6':'26', ...}，从以上可知，2和6一定会出现在A5和A6这两个位置（虽然我们不能确定具体是哪个位置），因此我们可以从A列单元中的其他位置中删除2和6这两个数字。我们可以通过编写if len(values[s]) == 2的测试语句来消除待定数字。
编写这些策略是可行的，但需要好多的代码量（因为有很多类似的策略），而且我们不敢肯定这就一定能解决所有的数独问题。
&翻译得不错哦！
解决数独的另一种方法是搜索，即遍历所有的可能性，直到有一个合适的数字填写方法为止。这种方法不需要编写大量的代码，但是需要花费很长的计算时间，有可能是永远。以上述grid2为例，A2有4种可能性（即数字“1679”）,A3有5种可能性（即数字“12679”）,如此乘下去，整个数独会有4. × 1038种可能性。我们该如何处理呢？以下介绍2种方法。
第一种方法是使用蛮力法。假设我们设计了一种非常高效的程序，该程序使用一条指令就可以计算一个位置，该程序运行在1024核的10GHz CPU，那么从13亿年前就运行该程序，那么到现在为止，仅完成1%的计算量。
&翻译得不错哦！
第二个选择是用某种方式是一条机器指令处理超过一种可能性.这似乎不可能, 但是幸运的是我们可以严谨的限制他的增长速度. 我们不必尝试全部的 4 × 1038 种可能性因为我们尝试了一个就排除了其他的可能. 例如,&这道谜题中的方格有两个可能性, 6 和 9. 我们可以尝试 9&很快就能看出有矛盾.&这就意味着,我们并不是指排除了一种可能性， 而是 4 × 1038&种选择的整整一半.
事实上,这表明我们要解决特定的谜题我们只需要查看25种可能性 而我们明确的知道直至需要遍历9-61个待填充方格;增长约束做了其他的工作.&在95道 的列表中 我们平均每道谜题需要考虑64种可能性,&并且至少需要遍历16个方格.
&翻译得不错哦！
查找算法是什么? 简单来说: 首先确认我们还没有找到一种正确或错误的解法, 如果找到了,&就选择一个未填充的方格和所有可能的数值.&每次尝试一个组合,在方格中分配每个数值, 从这基础上继续查找.&换句话说, 我们查找一个能够使我们在将d分配给某个方格的时候成功地找到解法的d值.如果查找失败就回退，并尝试另一个d值. 这是一种递归搜索, 我们称之为
因为在我们赋给s另一个值之前我们要 (遍历地) 尝试values[s] = d的全部可能性.
&翻译得不错哦！
我们的翻译工作遵照 ，如果我们的工作有侵犯到您的权益，请及时联系我们推荐到广播
650868 人聚集在这个小组
(半亩园长工)
第三方登录：扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
请问这道数独题目该怎么解,思路呢?&
卖萌无敌143
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
看不明白呀
假设最上面不是7，则按箭头方向所有方框里的数字都是真，则红圈里的7可以删除。想进一步了解可以去贴吧数独吧看置顶帖。
为您推荐：
其他类似问题
扫描下载二维码}