-2

このリンクには、数独ソルバー アルゴリズムのバックトラッキング実装があります。最初に割り当てられた値が有効な出力を与えなかった場合に備えて、行番号 42 がセルに最初に割り当てられた値を別の値に戻す方法に注意してください。

ただし、そのセルの値だけを変更するだけで十分であることがわかりません。この呼び出しは他の多くの呼び出しをトリガーする可能性があり、配列 (行列) はメモリ (参照) によって渡されるため、再帰関数の呼び出しごとに行列 (grid[N][N]) のコピーを保持しません。したがって、再帰の基本ケースが戻ってくるまでに再帰の最初のフレームにも反映されるまで変更されます。

私によると、再帰関数を呼び出す直前に、 grid[N][N] の一時的なコピーを作成し、呼び出しが返されたらすぐに、同じフレーム内の次の関数が呼び出される前に復元する必要があります。

何かのようなもの

for (int num = 1; num <= N; num++)
    {
        // if looks promising
        if (isSafe(grid, row, col, num))
        {
            //save grid state
            int[][] temp = new int[N][N];
            save(temp,grid); //copy all values from grid to temp             

            // make tentative assignment
            grid[row][col] = num;

            // return, if success, yay!
            if (SolveSudoku(grid))
                return true;

            //restore grid state           
            restore(temp,grid); //copy all values from temp back to grid

            // failure, unmake & try again
            grid[row][col] = UNASSIGNED;
        }
    }

この詳細を理解するのを手伝ってください。

4

1 に答える 1

3

状態を保存しています: 各再帰呼び出しは、状態を呼び出しスタックに保存します。

グリッドの割り当てられていない部分は、有効なソリューションが見つかるまで変更されます。それが完了すると、スタックされたすべての関数呼び出しが終了し (38 行目と 39 行目)、 はgrid[][]解決された状態のままになります。そうでない場合は、現在のセルをそのUNASSIGNED値に復元し、次の可能な値を試します。

これは力ずくのソルバーです。あなたもそれについてグーグルしたいかもしれません。

お役に立てれば。

于 2016-07-18T02:29:56.963 に答える