2

我正在玩我发现的这个数独求解器。

就像这里引用的一样，它工作得很好，但是如果我取消注释那个我注释掉的 single print a（第 13 行），那么它会在找到完整的解决方案之前停止......？

import sys
from datetime import datetime # for datetime.now()
 
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('.')
    if i == -1: # All solved !
        print a
    else:
        #print 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:
        filI = open(sys.argv[1])
        for pusI in filI:
            pusI.strip()
            print "pussle:\n",pusI
            timStart = datetime.now()
            r(pusI) # <- Calling the recursive solver ...
            timEnd = datetime.now()
            print "Duration (h:mm:ss.dddddd): "+str(timEnd-timStart)
    else:
        print str(len(sys.argv)) 
        print 'Usage: python sudoku.py puzzle'

程序需要用文件调用。该文件每行应包含 1 个数独。

对于测试，我使用了这个：

25...1........8.6...3...4.1..48.6.9...9.4.8...1..29.4.9.53.7....6..5...7.........

问题：

在完成之前，我无法理解那个单一的“打印 a”是如何打破递归循环的。谁能给个解释？

信用：我最初在这里找到了上面的数独求解器代码： http ://www.scottkirkwood.com/2006/07/shortest-sudoku-solver-in-python.html 它也显示在 StackOverflow 上： Shortest Sudoku Solver in Python -它是如何工作的？

4

1 回答 1

6

它确实找到了解决方案。我运行了程序并得到了解决方案

256491738471238569893765421534876192629143875718529643945387216162954387387612954

如果您按照建议运行取消注释并将其输出到文件：

python solver.py file.txt > output.txt

并搜索解决方案字符串，它就在那里。这不是最后一行，对我来说它在文件中显示了 67%。

这样做的原因是求解器基本上会经历大量组合并找到解决方案，但只要有任何可能的路径可以找到可能的解决方案，它就会继续。

于 2013-02-28T20:13:47.013 回答