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

Question

我在玩自己的数独解题器，想找一些好的快速设计建议，结果发现了这个：

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])

我自己的实现方式是用我脑子里解数独的方式，但这个神秘的算法是怎么工作的呢？

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

Answer 1

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 的所有数字（虽然效率不高）。

Answer 2

解密它：

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

所以，我们只需要搞清楚里面的列表表达式。我知道它会收集这一行中的数字集合——否则周围的代码就没意义了。不过，我现在真的不知道它是怎么做到的（而且我现在太累了，没力气去研究那些复杂的二进制东西，抱歉）

Answer 3

好吧，你可以通过修正语法让事情变得简单一些：

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 作为字符出现，它就不能作为替代，这只能在第一个表达式为零时发生。那么，什么时候这个表达式为零呢？

它有三个部分相乘：

• (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'