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

我自己的实现解决Sudokus的方式与我在头脑中解决它们的方式相同，但是这个神秘的算法是如何工作的呢？

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

Answer 1

好的，你可以通过修改语法来让事情变得更简单：

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等同于传递0，其他任何对象都会打印到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，用该字符串中的一个数字填充第一个空格。但只有当前面的表达式为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，则相同的column.
• (i/9^j/9)为零；即，如果这两个row.
• (i/27^j/27|i%9/3^j%9/3)都为zero:
• ​
  • i/27^j^27，则相同的rows

为零；如果i/27 == j/27，则==为零；即，三个rows的相同块

​

如果i%9/3

• ​
  • i%9/3^j%9/3 j%9/3，即三个columns

的相同块，则==为零

​

如果这三个部分中的任何一个为零，则整个表达式为零。换句话说，如果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'

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

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“。这是最棘手的一点。:)

is_bad or r(a[:i]+m+a[i+1:]是一个条件递归步骤。它将递归地尝试评估董事会中的下一个0，如果当前的解决方案候选似乎是合理的。

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