Python中最短的数独求解器 - 它是如何工作的？

我正在玩我自己的数独求解器,当我遇到这个时,我正在寻找一些指向良好和快速设计的指针:

def r(a):i=a.find('0');~i or exit(a);[m
in[(i-j)%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,就像我在头脑中解决它一样,但这个神秘的算法是如何工作的？

http://scottkirkwood.blogspot.com/2006/07/shortest-sudoku-solver-in-python.html

1> Bill Barksda..：

---

好吧,你可以通过修改语法使事情变得更容易:

def r(a):
  i = a.find('0')
  ~i or exit(a)
  [m in[(i-j)%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[(i-j)%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.如果该字符串中没有零,则r退出并打印出其参数.

(如果传递了另一种类型的对象,则None等效于传递零,并且任何其他对象将打印到sys.stderr并导致退出代码为1.特别是,sys.exit("某些错误消息")是一个发生错误时快速退出程序.请参阅 http://www.python.org/doc/2.5.2/lib/module-sys.html)

我想这意味着零对应于开放空间,并且解决了没有零的拼图.那就是令人讨厌的递归表达式.

循环很有趣: for m in'%d'%5**18

为什么5**18？事实证明,'%d'%5**18评估为'3814697265625'.这是一个字符串,每个数字1-9至少有一次,所以也许它正试图放置它们中的每一个.事实上,看起来这就是r(a[:i]+m+a[i+1:])正在做的事情:递归调用r,第一个空白用该字符串中的数字填充.但这只有在前面的表达式为假时才会发生.我们来看看:

m in [(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)]

因此,只有当m不在该怪物列表中时才进行放置.每个元素都是一个数字(如果第一个表达式非零)或一个字符(如果第一个表达式为零).如果m显示为一个字符,则m被排除为可能的替换,只有在第一个表达式为零时才会发生.表达式何时为零？

它有三个部分相乘:

(i-j)%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 如果i%9/3 == j%9/3,则为零,即三列相同的块

如果这三个部分中的任何一个为零,则整个表达式为零.换句话说,如果i和j共享行,列或3x3块,则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 (i-j)%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将返回并返回到可以选择其他内容的点,因此它是一个基本的深度优先算法.

不使用任何启发式方法,它不是特别有效.我从维基百科(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 (i-j) % 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'

---

@JoshBibb我知道这是一篇旧帖子,但是这个错误正在发生,因为这是为Python2编写的,你在Python3中运行它.用`//`运算符替换`same_row`,`same_col`和`same_block`中的所有`/`运算符,你就会得到正确的答案.

---

只是为了明确,你可能想把`i%9/3 == j%9/3`改为`(i%9)/ 3 ==(j%9)/ 3`.我知道你应该用心去了解操作员的顺序,但它很容易忘记并且使扫描更容易一些.

---

@GundarsMēness在递归的每个点处,处理一个空位置.如果找不到该位置的有效数字,则该函数返回.这意味着,如果找不到第一个空位置的有效数字(即输入是无效的数独),整个程序将返回没有输出(从未到达`sys.exit(a)`)

2> Tetha..：

---

不加掩饰:

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 = [ (i-j)%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

所以,我们只需要计算内部列表表达式.我知道它收集行中设置的数字 - 否则,它周围的代码没有任何意义.但是,我不知道它是如何做到的(而且我太累了,现在不能弄清楚那个二进制的幻想,对不起)

3> Deestan..：

---

r(a)是一个递归函数,它试图0在每一步中填写一个板.

i=a.find('0');~i or exit(a)是成功终止.如果0董事会中不存在更多价值,我们就完成了.

m是我们将尝试填补的当前值0.

m in[(i-j)%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:]是一个有条件的递归步骤.0 如果当前的候选解决方案似乎是理智的话,它将递归地尝试评估板中的下一个.

for m in '%d'%5**18 枚举从1到9的所有数字(效率低下).