2

私が見つけたこの数独ソルバーで遊んでいました。

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行に1つの数独を保持する必要があります。

テストにはこれを使用しました：

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

質問：

その単一の「printa」がどのように再帰ループを壊すことができるのか、それが完了する前に理解できません。誰か説明してもらえますか？

クレジット：私はもともと上記の数独ソルバーコードをここで見つけました： http ：//www.scottkirkwood.com/2006/07/shortest-sudoku-solver-in-python.html StackOverflow： Pythonで最短の数独ソルバーにも表示されます-それはどのように機能しますか？

4

1 に答える 1

6

それは実際に解決策を見つけます。私はプログラムを実行し、解決策を得ました

256491738471238569893765421534876192629143875718529643945387216162954387387612954

あなたが提案したようにコメントを外して実行し、それをファイルに出力すると：

python solver.py file.txt > output.txt

ソリューション文字列を検索すると、そこにあります。これは最後の行ではありません。私にとっては、ファイルに 67% 表示されます。

これを行う理由は、ソルバーが基本的に大量の組み合わせを調べて解を見つけますが、可能性のある解を見つけるために下る可能性のあるパスがある限り続行するためです。

于 2013-02-28T20:13:47.013 に答える