2

最近、再帰とバックトラックを理解するためにいくつかの質問を投稿しました。今何かを得たと感じ、テストを書き込もうとしました。数独の問題は解決しましたが、別の形式でコードを書くと、コードが動かなくなります。 while と False を返します。これは、この問題の解決策がないことを示します。

grid は 9x9 のリストのリストです。list[i][j] がゼロの場合は、入力する必要があることを意味します。

問題を解決したコードは次のとおりです。

def correct_solve(grid):

    # if there is no more zeros
    if found_solution(grid):
        return True

    for row in xrange(9):
        for col in xrange(9):
            if grid[row][col] == 0:
                for num in xrange(1, 10):
                    grid[row][col] = num
                    if check_sudoku(grid) == True:
                        if correct_solve(grid) == True:
                            return True
                # there are no numbers which could make
                # a valid solution, so backtrack
                grid[row][col] = 0
                return False

そして、別の方法で問題を解決しようとした別の機能がありますが、失敗し、どこに問題があるのか​​ わかりませんでした

def buggy_solve(grid, col):

    # if there is no more zeros
    if found_solution(grid):
        return True

    # if the col is over 8, make it to 0
    if col > 8:
        col = 0

    for row in xrange(9):
        if grid[row][col] == 0:
            for num in xrange(1, 10):
                grid[row][col] = num
                if check_sudoku(grid) == True:
                    # I tend to move to the next cell, and it seems that
                    # this is correct.
                    if buggy_solve(grid, col + 1) == True:
                        return True

            # if there are no valid solutions, backtrack.
            grid[row][col] = 0
            return False

プログラムをデバッグしようとしましたが、有用なものは何も見つかりませんでした。ところで、再帰コードをデバッグするための良い方法はありますか?

編集：

テストに使用しているマトリックスは次のとおりです。

easy = [[2,9,0,0,0,0,0,7,0],
        [3,0,6,0,0,8,4,0,0],
        [8,0,0,0,4,0,0,0,2],
        [0,2,0,0,3,1,0,0,7],
        [0,0,0,0,8,0,0,0,0],
        [1,0,0,9,5,0,0,6,0],
        [7,0,0,0,9,0,0,0,1],
        [0,0,1,2,0,0,3,0,6],
        [0,3,0,0,0,0,0,5,9]]
4

2 に答える 2

1

correct_solveグリッド全体をbuggy_solve調べ、1 つの列を調べます。これは、問題がまだ解決されていない場合buggy_solve、現在の列のみを検索してセルを埋めることを意味します。その列に空のセルがない場合、外側の for ループから外れます。明示的なreturnステートメントを使用せずに終了します。buggy_solveしたがって、これが発生したときに次の列で呼び出すコードが必要になります (そして適切なreturnステートメントを使用します)。

于 2012-07-18T09:59:01.360 に答える
0

問題は、再帰的なソリューションがバックトラックを開始しないことです。代わりに、誤って解決策を見つけない限り、無限の再帰に終わります。これは非常にありそうもなく、ほとんど解決された数独でのみ機能します。それらの状況を取り上げると、これが起こっていることです：

if buggy_solve(grid, col + 1) == True:
    return True

このbuggy_solve呼び出しがfalse を返すことはありません。関数は、必要に応じて列を試行および反復し続けるためです。そして、最後の列に到達すると、最初の列から再び開始され、以前に発生したすべてが上書きされます。

そのため、バックトラッキングが開始されることはありません。check_sudokuまだ処理の初期段階にあることを考えると、めったに失敗することはなく、ほとんど埋められていない数独では、特定のセルに複数の値が許可される可能性があります。

buggy_solveつまり、列のリセットを削除し、無効な列に対して単純に false を返すようにします。そうbuggy_solveすれば、ある時点で false が返され、バックトラッキングが実際に開始されます。

于 2012-07-18T10:38:53.513 に答える