1 
def answer_solve_sudoku(__grid):

    res = check_sudoku(__grid)
    if res is None or res is False:
        return res

    grid = copy.deepcopy(__grid)

    # find the first 0 element and change it to each of 1..9,
    # recursively calling this function on the result
    for row in xrange(9):
        for col in xrange(9):
            if grid[row][col] == 0:
                for n in xrange(1, 10):
                    grid[row][col] = n
                    new = answer_solve_sudoku(grid)
                    if new is not False:
                        return new
                # backtrack
                return False

    # if we get here, we found no zeros and so we're finished
    return grid

コードはcheck_sudoku(grid)次のとおりです。グリッドが有効な数独かどうかを返すことができます。

再帰の部分だけ理解できなくて、プロセスを紙に書き留めようとしたのですが、毎回失敗しました。とは何newですか？が有効な場合answer_solve_sudoku(grid)は？

0 から 1..9 ごとに設定し、有効なグリッドかどうかを確認することは知っていますが、プロセス全体を紙に描くことはできません。そして、バックトラックがどのように機能するかを本当に理解できません。

ところで、再帰コードを理解するためのアドバイスはありますか?

よろしくお願いします、

シェン・ユン

編集

私はコードを何度も何度も読みましたが、今ではある程度理解していますが、これについてはよくわかりません。誰かがコメントをくれれば親切です。

1、return newソルバーが解を見つけたときにのみ呼び出され、これはその直後に呼び出されますreturn grid

2、いつになるか

# backtrack
return False

呼ばれる？次の解が正しくない場合はcheck_sudoku(__grid)を返し、次の解が正しければ、正しい解が得られるまでFalse別の解を呼び出し、正しい解が得られるとを呼び出します。だからいつ：answer_solve_sudoku(grid)return gridreturn new

# backtrack
return False

呼ばれた？

4

2 に答える 2

1

これを紙に書くよりも、私にはもっと良い推薦があります。コードをフォーマットして、ロジックが実行していることを視覚的に表現します。これを行う方法は次のとおりです。

def print_counter(val, msg):
    print "%s[%d] %s" % (" "*val, val, msg)

def answer_solve_sudoku(__grid, counter=0):

    res = check_sudoku(__grid)
    if res is None or res is False:
        return res

    grid = copy.deepcopy(__grid)

    for row in xrange(9):
        for col in xrange(9):
            if grid[row][col] == 0:
                for n in xrange(1, 10):
                    grid[row][col] = n
                    print_counter(counter,"test: (row %d, col %d) = %d" % (row,col,n))
                    new = answer_solve_sudoku(grid, counter+1)
                    if new is not False:
                        print_counter(counter, "answer_solve_sudoku() solved: returning")
                        return new
                # backtrack
                print_counter(counter, "backtrack")
                return False

    print_counter(counter, "**SOLVED! Returning back up to top**")
    return grid

from pprint import pprint 
solution = answer_solve_sudoku(easy_grid)
pprint(solution)

私がしたことは、数字を印刷し、その数のスペースでメッセージをインデントする小さなプリンター関数を作成することでした。次に、のでanswer_solve_sudoku、デフォルトのカウンター値0を指定し、各再帰呼び出しに常にcounter+1を渡します。そうすれば、深さが増すにつれて、数も増えます。そして、何が起こっているのかを視覚的に説明するために、プリンター機能を使用しています。

表示されるのは次のようなものです。

[0] test: (row 0, col 2) = 1
[0] test: (row 0, col 2) = 2
[0] test: (row 0, col 2) = 3
[0] test: (row 0, col 2) = 4
 [1] test: (row 0, col 3) = 1
  [2] test: (row 0, col 4) = 1
  [2] test: (row 0, col 4) = 2
  [2] test: (row 0, col 4) = 3
    ... 
         [45] test: (row 7, col 7) = 8
         [45] test: (row 7, col 7) = 9
         [45] backtrack
        [44] test: (row 7, col 5) = 6
        [44] test: (row 7, col 5) = 7
    ... 
               [51] test: (row 8, col 6) = 6
               [51] test: (row 8, col 6) = 7
                [52] **SOLVED! Returning back up to top**
               [51] answer_solve_sudoku() solved: returning
              [50] answer_solve_sudoku() solved: returning
             [49] answer_solve_sudoku() solved: returning
    ... 
  [2] answer_solve_sudoku() solved: returning
 [1] answer_solve_sudoku() solved: returning
[0] answer_solve_sudoku() solved: returning

return newは、ソルバーが解を見つけたときにのみ呼び出され、これはreturngridの直後に呼び出されます。

はい、への呼び出しがanswer_solve_sudoku失敗することなくそのループ全体を通過し、最下部に到達すると、成功してグリッドを返します。呼び出し元は、結果としてそのグリッドを取得し、それnew = answer_solve_sudoku(grid)を返します。グリッドは、スタックに戻ってくる各呼び出しをバックアップします。

バックトラックはいつ発生しますか？

各再帰でグリッドのコピーを作成しているため、そのステップで解決策が見つからない限り、そのグリッドに加えられた変更は破棄されます。これは、1つのステップに戻ると、前のグリッド状態に戻るためです。値9を超えるまで、そのソリューションで可能な限り実行しようとします。

于 2012-07-17T18:00:41.967 に答える
1

この答えをチェックする必要があります。再帰的なバックトラック用の擬似コードと実際のコードがあります。コードはJavaですが、Pythonの場合と同じ思考プロセスです。

于 2012-07-17T18:01:43.933 に答える