Python中最短的数独求解器 – 它是如何工作的？
当我遇到这个问题时，我正在玩我自己的数独求解器，并正在寻找一些好的和快速devise的指针：
def r(a):i=a.find('0');~i or exit(a);[m in[(ij)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18] from sys import*;r(argv[1]) 我自己的实现以我在脑海中解决他们的方式解决Sudokus，但是这个神秘的algorithm是如何工作的？
http://scottkirkwood.blogspot.com/2006/07/shortest-sudoku-solver-in-python.html
那么，通过修正语法，可以使事情变得更容易：
def r(a): i = a.find('0') ~i or exit(a) [m in[(ij)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)] or r(a[:i]+m+a[i+1:])for m in'%d'%5**18] from sys import * r(argv[1])
清理一下：
from sys import exit, argv def r(a): i = a.find('0') if i == -1: exit(a) for m in '%d' % 5**18: m in[(ij)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)] or r(a[:i]+m+a[i+1:]) r(argv[1])
好的，所以这个脚本需要一个命令行参数，并调用它的函数r。 如果该string中没有零，则r退出并打印出其参数。
（如果传递了另一种types的对象，则None等同于传递零，而其他任何对象都被打印到sys.stderr并导致退出代码为1.特别是，sys.exit（“some error message”）是一个发生错误时快速退出程序。请参阅http://www.python.org/doc/2.5.2/lib/module-sys.html ）
我想这意味着零对应于开放空间，而一个没有零的难题就解决了。 那就是那个讨厌的recursionexpression式。
循环很有意思： for m in'%d'%5**18
为什么5 ** 18？ 事实certificate'%d'%5**18评估为'3814697265625' 。 这是一个string，每个数字1-9至less有一次，所以也许它试图放置每个数字。 实际上，它看起来像是r(a[:i]+m+a[i+1:])正在做的事情：recursion地调用r，第一个空格由该string中的一个数字填充。 但是，只有在早期的expression式是错误的时候才会发生 我们来看看：
m in [(ij)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)]
所以只有当m不在怪物列表中时才进行放置。 每个元素可以是一个数字（如果第一个expression式不是零）或一个字符（如果第一个expression式为零）。 如果它作为一个字符出现，m将被排除为可能的replace，只有当第一个expression式为零时才会发生。 什么时候expression式为零？
它有三个部分相乘：
-
(ij)%9，如果i和j是9的倍数，即同一列，那么它是零。 -
(i/9^j/9)，如果i / 9 == j / 9，即同一行，则为零。 -
(i/27^j/27|i%9/3^j%9/3)，如果这两个都是零， -
-
i/27^j^27如果i / 27 == j / 27则为零，即三行的同一个块
-
-
-
i%9/3^j%9/3，如果是％9/3 == j％9/3，即三列
-
如果这三个部分中的任何一个为零，则整个expression式为零。 换句话说，如果i和j共享一个行，列或3×3块，那么j的值不能用作i的空白候选项。 啊哈！
from sys import exit, argv def r(a): i = a.find('0') if i == -1: exit(a) for m in '3814697265625': okay = True for j in range(81): if (ij)%9 == 0 or (i/9 == j/9) or (i/27 == j/27 and i%9/3 == j%9/3): if a[j] == m: okay = False break if okay: # At this point, m is not excluded by any row, column, or block, so let's place it and recurse r(a[:i]+m+a[i+1:]) r(argv[1])
请注意，如果没有任何展示位置出现，r会返回并返回到可以select其他位置的位置，因此这是基本的深度优先algorithm。
不使用任何启发式，它不是特别有效。 我从维基百科（ http://en.wikipedia.org/wiki/Sudoku ）处理了这个难题：
$ time python sudoku.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079 534678912672195348198342567859761423426853791713924856961537284287419635345286179 real 0m47.881s user 0m47.223s sys 0m0.137s
附录：如何将其重写为维护程序员（该版本的速度大约是93倍）
import sys def same_row(i,j): return (i/9 == j/9) def same_col(i,j): return (ij) % 9 == 0 def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3) def r(a): i = a.find('0') if i == -1: sys.exit(a) excluded_numbers = set() for j in range(81): if same_row(i,j) or same_col(i,j) or same_block(i,j): excluded_numbers.add(a[j]) for m in '123456789': if m not in excluded_numbers: # At this point, m is not excluded by any row, column, or block, so let's place it and recurse r(a[:i]+m+a[i+1:]) if __name__ == '__main__': if len(sys.argv) == 2 and len(sys.argv[1]) == 81: r(sys.argv[1]) else: print 'Usage: python sudoku.py puzzle' print ' where puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank'
不混淆它：
def r(a): i = a.find('0') # returns -1 on fail, index otherwise ~i or exit(a) # ~(-1) == 0, anthing else is not 0 # thus: if i == -1: exit(a) inner_lexp = [ (ij)%9*(i/9 ^ j/9)*(i/27 ^ j/27 | i%9/3 ^ j%9/3) or a[j] for j in range(81)] # r appears to be a string of 81 # characters with 0 for empty and 1-9 # otherwise [m in inner_lexp or r(a[:i]+m+a[i+1:]) for m in'%d'%5**18] # recurse # trying all possible digits for that empty field # if m is not in the inner lexp from sys import * r(argv[1]) # thus, a is some string
所以，我们只需要制定内部列表expression式。 我知道它收集在行中设置的数字 – 否则，围绕它的代码是没有意义的。 但是，我没有真正的线索是如何做到这一点（我现在太累了，现在没有解决二进制幻想，对不起）
r(a)是一个recursion函数，它试图在每一步中填充一个0 。
i=a.find('0');~i or exit(a)是在成功终止。 如果电路板中不存在更多的值，我们就完成了。
m是当前值，我们将尝试填充0 。
m in[(ij)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)]如果把m放在当前的0是明显不正确的，则评价为真。 我们昵称“is_bad”。 这是最棘手的一点。 🙂
is_bad or r(a[:i]+m+a[i+1:]是一个有条件的recursion步骤，如果当前的解决scheme候选者似乎是理智的，它将recursion地尝试评估板中的下一个0 。
for m in '%d'%5**18列举了从1到9（低效）的所有数字。
很多短数独求解器recursion地尝试每一个可能的合法数字，直到他们成功地填充单元格为止。 我没有把这个分开，只是略读而已，看起来就是这样。
代码实际上不工作。 你可以自己testing一下。 这是一个未解决的数独拼图示例：
807000003602080000000200900040005001000798000200100070004003000000040108300000506
您可以使用这个网站（ http://www.sudokuwiki.org/sudoku.htm ），点击导入拼图，只需复制上面的string。 python程序的输出是：817311213622482322131224934443535441555798655266156777774663869988847188399979596
这不符合解决scheme。 其实你已经可以看到一个矛盾了，第一排是两个1。
