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

疏通它：

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 2

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

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退出并输出其参数。

(If another type of object is passed, None is equivalent to passing zero, and any other object is printed to sys.stderr and results in an exit code of 1. In particular, sys.exit("some error message") is a quick way to exit a program when an error occurs. See 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，第一个空格由该字符串中的一个数字填充。但只有在前面的表达式为false时才会发生这种情况。让我们看看：

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的值不能用作IAHA中的空白的候选。

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将返回并返回到可以选择其他内容的点，因此这是一个基本的深度优先算法。

不使用任何启发式方法，就不是特别有效。我从维基百科（Wikipedia）上找到这个拼图：

$ time python sudoku.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079
534678912672195348198342567859761423426853791713924856961537284287419635345286179

real    0m47.881s
user    0m47.223s
sys 0m0.137s

附录：我将如何重写它作为一个维护程序员（这个版本有大约93x的加速：）

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'

Answer 3

r(a)是一个递归函数，它试图在每个步骤中在电路板中填充一个0。

i=a.find('0');~i or exit(a)是成功时终止。如果电路板中不再存在0值，我们就完成了。

m是当前值，我们将尝试用它填充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)]计算为truthy。让我们给它取个绰号“不好”。这是最棘手的一点。：）

is_bad or r(a[:i]+m+a[i+1:]是一个条件递归步骤。它将递归地尝试评估董事会中的下一个0，前提是当前的候选解决方案看起来是正常的。

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