このリンクには、数独ソルバーアルゴリズムのバックトラッキング実装があります。最初に割り当てられた値が有効な出力を提供しなかった場合、行番号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;
}
}
この詳細を理解するのを手伝ってください。
それはされた状態を保存:各再帰呼び出しは、呼び出しスタック上の状態を保存します。
グリッドの割り当てられていない部分は、有効なソリューションが見つかるまで変更されます。完了すると、スタックされたすべての関数呼び出しが終了し(38行目と39行目)、grid[][]
が解決された状態のままになります。そうでない場合は、現在のセルをそのUNASSIGNED
値に復元し、次の可能な値を試行します。
これはブルートフォースソルバーです。あなたはそれについてもグーグルしたいかもしれません。
お役に立てれば。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加