我在玩自己的Sudoku求解器时，遇到以下问题时正在寻找一些指向快速，好设计的指针:
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
最佳答案
好了，您可以通过修复语法来使事情变得容易一些:
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退出并输出其参数。
我想这意味着零对应于开放空间，并且解决了没有零的难题。然后就是讨厌的递归表达式。
循环很有趣:
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的值不能用作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'
关于python - Python中最短的数独求解器-如何工作？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/201461/