Thisリンクには、Sudoku Solverアルゴリズムのバックトラッキング実装があります。最初に割り当てられた値が有効な出力を与えなかった場合、行番号42がセルに最初に割り当てられた値を別の値に戻す方法に注目してください。状態を保存していないにもかかわらず、このSudokuソルバの実装はどのように機能しますか?
しかし、単にそのセルの値を変更するだけで十分であるとは私は理解していません。この呼び出しは、配列(行列)がメモリ(参照)によって渡されるため、他の多くの呼び出しを引き起こした可能性があります。は、再帰的な呼び出しのたびに行列のコピー(グリッド[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;
}
}
よう
何か。
コードの残りの部分を検証せずに正式な回答を提供することはできません。しかし、stackoverflow.comは本当にこれのための場所ではありません。 「UNASSIGNED」割り当てが移動を元に戻すように見えるので、元のグリッドのバックコピーは不要であるように見えますが、やはり100%の確実性ではっきり言ってはいけません。しかし、これはまさにデバッガのためのものです。あなたのコンピュータ上にあるこの非常に便利なツールを使用して、一度に1行ずつこのコードをステップ実行し、インターネットで見知らぬ人に助けを求めることなく、どのように動作するのかを見てください。 –
再帰の各レベルで、コードは1つのセルを割り当て、1つのセルを元に戻します。グリッド全体を格納する必要はありません。元の状態は、各再帰呼び出しが戻った後に一度に1つのセルに復元されるからです。完全な状態は、コールスタック、ローカル変数rowおよびcolに格納され、それぞれの再帰レベルで保存されます。 – samgak