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。