1

Python 言語で書かれた数独ソルバーを次に示します。このプログラムを実行すると、Update 関数と Solve 関数に問題があるようです。

どれだけコードを調べて動かしても、運が悪いようです

誰でも私を助けることができますか？

import copy


def display (A):

    if A:
        for i in range (9):
            for j in range (9):
                if type (A[i][j]) == type ([]): print A[i][j][0],
                else: print A[i][j]
            print
        print
    else: print A

def has_conflict(A):

    for i in range(9):
        for j in range(9):
            for (x,y) in get_neighbors(i,j):
                if len(A[i][j])==1 and A[i][j]==A[x][y]: return True
    return False


def get_neighbors(x,y):

    neighbors = []
    for i in range(3):
        for j in range(3):
            a = 3*(x / 3)+i
            b = 3*(y / 3)+j
            if (x,y) != (a,b):
                neighbors += [(a,b)]

    for i in range(9):
        if (x,y) != (x,i) and (x,i) not in neighbors:
            neighbors += [(x,i)]
        if (x,y) != (i,y) and (i,y) not in neighbors:
            neighbors += [(i,y)]

    return neighbors



def update(A,x,y,value):

    B = copy.deepcopy(A)
    B[x][y] = [value]
    for (i,j) in get_neighbors(x,y):
        if B[i][j] == B[x][y]:
            if len(B[i][j]) > 1: B[i][j].remove(value)
            else: return [] 
    if has_conflict(B) == True: return []
    else: return B


def solve(A):

    for x in range (9):
        for y in range(9):
            if len(A[x][y]) == 1: return A[x][y]
            if len(A[x][y]) > 1:
                lst = update(A,x,y,A[x][y])
                if len(lst[x][y]) > 1: solve(lst)
                if lst == []: return []
                if len(lst[x][y]) == 1: return lst
            else: return A[x][y]    



A=[]

infile = open('puzzle1.txt','r')

for i in range(9):

        A += [[]]
        for j in range(9):
            num = int(infile.read(2))
            if num: A[i] += [[num]]
            else: A[i] += [[1,2,3,4,5,6,7,8,9]]

for i in range(9):

        for j in range(9):
            if len(A[i][j])==1: A = update(A, i, j, A[i][j][0])
            if A == []: break
        if A==[]: break

if A<>[]: A = solve(A)

display(A)

ここにいくつかのパズルがあります：

パズル 1

0 0 0 2 6 0 7 0 1
6 8 0 0 7 0 0 9 0
1 9 0 0 0 4 5 0 0
8 2 0 1 0 0 0 4 0
0 0 4 6 0 2 9 0 0
0 5 0 0 0 3 0 2 8
0 0 9 3 0 0 0 7 4
0 4 0 0 5 0 0 3 6
7 0 3 0 1 8 0 0 0

パズル 2

1 0 0 4 8 9 0 0 6
7 3 0 0 0 0 0 4 0
0 0 0 0 0 1 2 9 5
0 0 7 1 2 0 6 0 0
5 0 0 7 0 3 0 0 8
0 0 6 0 9 5 7 0 0
9 1 4 6 0 0 0 0 0
0 2 0 0 0 0 0 3 7
8 0 0 5 1 2 0 0 4

パズル 3

0 2 0 6 0 8 0 0 0
5 8 0 0 0 9 7 0 0
0 0 0 0 4 0 0 0 0
3 7 0 0 0 0 5 0 0
6 0 0 0 0 0 0 0 4
0 0 8 0 0 0 0 1 3
0 0 0 0 2 0 0 0 0
0 0 9 8 0 0 0 3 6
0 0 0 3 0 6 0 9 0
4

4 に答える 4

3

コードを安定させたい場合は、関数ごとに小さなテストケースを作成して、正しく機能することを確認します。

あなたの場合、パズルを実行して、どのフィールドが間違っているかを判断します。次に、どの関数が間違った出力を生成する可能性があるかを推測します。入力を使用して呼び出し、実際に何をするかを確認します。見つけたすべてのバグについて繰り返します。

[編集]モジュールunittestはあなたの友達です。

于 2009-11-23T08:55:12.327 に答える
3

「コードを移動する」などは避けたいと思います。これは「偶然の一致によるプログラミング」と呼ばれます（実用的なプログラマーを参照）。このようなプログラミングは、あなたをより良いプログラマーにすることにはなりません。

代わりに、紙と鉛筆を取り出して、物事がどのように機能するかを考え始める必要があります。次に、コードを読み、実際に何をするかを注意深く記述します。理解したときだけ、コンピュータ端末に戻ってください。

于 2009-11-23T09:04:21.573 に答える
2

実際のコードを書いていただけるようにお手伝いしたいと思いますので、ここにいくつかの説明といくつかの疑似コードを示します。

人間の推論ロジックを模倣しない数独ソルバーは、ブルートフォース ベースです。基本的に、バックトラック アルゴリズムが必要です。has_conflict メソッドがあります。これは、候補者が一見して大丈夫かどうかをチェックします。次に、バックトラック アルゴリズムを次のように記述します。

Solve(s):
    Pick a candidate.
    Does it have a conflict? If yes, go back, and pick another one.
    No more empty cells? Then cool, return True.
    Have you run out of candidates? Then it cant be solved, return False.

    At this point, it seems ok. So call Solve(s) again, lets see how it works 
    out with the new candidate.
    If Solve returned false, then after all it was a bad candidate. Go
    back to picking another one.
    If Solve returned True, then you solved the sudoku!

ここでの主な考え方は、最初は競合がなくても、推測が間違っていた場合、呼び出しツリーのどこかで競合が明らかになるということです。

元の数独の解は 1 つだけです。Solve の戻り値に関係なく、任意の候補を試すことにより、このメソッドを数独のさまざまなソリューションに拡張できます (ただし、このアプローチでは非常に遅くなります)。

数独に複数の解があるかどうかを調べるための便利なトリックがあります。最初に、ソルブのすべての呼び出しで候補を自然な順序で試します。次に、それらを逆方向に試します。次に、これらの 2 つの手順をもう一度実行しますが、今回は数独の最後のセルからアルゴリズムを実行し、後ろ向きに進めます。これら 4 つの解が同一である場合、解は 1 つしかありません。残念ながら、正式な証明はありませんが、常に機能しているように見えました。私はそれを証明しようとしましたが、私はグラフが得意ではありません。

于 2009-11-23T10:03:06.680 に答える
0

数独を解決するには、ブルートフォース メソッドが必要です。コードにそれらが表示されません。

私も以前にやろうとしましたが、最終的にノーヴィグのコードを見ました。完璧に機能しています。

そしてついに彼のコードを学ぶことになりました。

于 2009-11-23T08:41:48.930 に答える