python - 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')
  ~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，第一个空格用一个数字填充从那个字符串。但这只发生在前面的表达式为假的情况下。让我们看看:

m in [(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) 或 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 则为零，即三行的同一 block
• • i%9/3^j%9/3 如果 i%9/3 == j%9/3 则为零，即三列的同一 block

如果这三个部分中的任何一个为零，则整个表达式为零。换句话说，如果 i 和 j 共享一个行、列或 3x3 block ，则 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 将返回并返回到可以选择其他位置的位置，因此这是一种基本的深度优先算法。

不使用任何启发式方法，它不是特别有效。我从 Wikipedia (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'