C++での再帰的なバックトラッキング

Question

バックトラックを使用してSudokuソルバーを作成するプログラムを作成しようとしています。私は黒い数独グリッドを作成することができ、移動が有効な移動であるかどうかを確認することができます。私のプログラムは、正方形に対して複数の選択肢があるまでうまく動作します。

問題：私のSolveメソッドを見て、それを修正してバックトラックし、答えを変更し、再び前進する方法を見てください。私は上記のすべての他の方法の名前とそれらの仕事のすべてを与えました。

例入力：

int board[ROWS][COLS] = { 
    { 6, 0, 3, 0, 2, 0, 0, 9, 0 }, 
    { 0, 0, 0, 0, 5, 0, 0, 8, 0 }, 
    { 0, 2, 0, 4, 0, 7, 0, 0, 1 }, 
    { 0, 0, 6, 0, 1, 4, 3, 0, 0 }, 
    { 0, 0, 0, 0, 8, 0, 0, 5, 6 }, 
    { 0, 4, 0, 6, 0, 3, 2, 0, 0 }, 
    { 8, 0, 0, 2, 0, 0, 0, 0, 7 }, 
    { 0, 1, 0, 0, 7, 5, 8, 0, 0 }, 
    { 0, 3, 0, 0, 0, 6, 1, 0, 5 } 
}; 

bool sudokuBoard::emptyCell(int i, int j); 

bool sudokuBoard::isValidCol(int i, int j, int number); 

bool sudokuBoard::isValidRow(int i, int j, int number); 

bool sudokuBoard::isValidSquare(int i, int j, int number); 

bool sudokuBoard::validMove(int i, int j, int number); 

void sudokuBoard::solvePuzzle(int row, int col) { 

    for (int i = 1; i < 10; i++) { 
     if (validMove(row, col, i)) { 
      board[row][col] = i; 
      showBoard(); 
     } 
    } 
    if (row < 8 && col < 8) { 
     if (col < 8) { 
      solvePuzzle(row, col + 1); 
     } 
     else { 
      col = 0; 
      solvePuzzle(row + 1, col); 
     } 
    } 
} 

例電流出力：

6 5 3| 1 2 8| 4 9 0| 
    0 0 0| 0 5 0| 0 8 0| 
    0 2 0| 4 0 7| 0 0 1| 
-------------------------------- 
    0 0 6| 0 1 4| 3 0 0| 
    0 0 0| 0 8 0| 0 5 6| 
    0 4 0| 6 0 3| 2 0 0| 
-------------------------------- 
    8 0 0| 2 0 0| 0 0 7| 
    0 1 0| 0 7 5| 8 0 0| 
    0 3 0| 0 0 6| 1 0 5| 

7にその前4が変化しない限り、解が存在しないので、私のプログラムは、最初の行の最後の0で停止し、プログラムは終了する。

Answer 1

バックトラックは、私たちは、あなたが今持っているものについてのいくつかの擬似コードで始まるステップによって、この手順を行う最初の頃のあなたの心をラップするのは難しいことができます：

while(puzzlenotsolved) 
    { 
    foreach row 
     { 
     findEmptySquare 
     { 
     findValidMove(1-9) 
     } 
     } 
    } 

これはもちろん、一旦有効なスタックなかっます以前選択された値のために四角形の移動が見つかります。

これに対処するには、正方形内で有効な移動がなくなったときにfalseを返す必要があります。また、正方形を空にするために推測を解除する必要があります。前の四角でループを再開する必要があります。あなたの質問を取得することができますのために今これは強引なアプローチと考えられている

bool findValidMove 
{ 
    if(noEmptySquare) {return true;} //important bit 

    findEmptySquare() 
    for (1-9) 
     { if (isvalidMove) 
      { 
       assignMoveToSquare 
      } 
      if (findValidMove) {return true} //important bit 

     unassignMoveFromSquare 
     } 
    return false; //no values valid in this square, a previous square has a wrong value 
} 

、および最適化することができますが、：

だから私たちの発見に有効な移動機能（あなたのケースでパズルを解く）は、このようなものを見ることができますあなたが望むなら、後で速度の最適化について心配することができます。

重要なビットとしてコメントした2つの場所に注意してください。最初は、空白の四角が残っていないことを示す記号です。あなたのプログラムは有効な動きしか割り当てていないので、ここでパズルは完全で正しいものでなければならないので、プログラムは真を返します。これは基本ケースです。一般に、再帰関数は基本ケースを必要とします。

2番目の重要なビットは、関数が再帰的に自身を呼び出す場所です。まだループ内にあることに注意してください。コールがfalseを返すと、以前の呼び出しでループが再開されます。私たちの例がループに戻ってくることを除いて、それぞれの呼び出しはthis exampleのようにもう一方にスタックします。

再帰関数が返されるまで、セルが割り当て解除されないことに注意してください。これにより、コメントに記述したように行と列に1を追加する心配がありません。信頼できるfindEmptySquareメソッドがあり、再帰が残りの部分を処理するだけです。

あなたshowBoard();方法は、デバッグのために非常に貴重になり、私はうまくいけば、これはあなたがそう、私はそれがなると思う本当に接近している、助け右assignMoveToSquare

後にそれを置くと思います。あなたはさらに質問がある場合は、これについてコメントして自由に感じてください、私は時間があるときにあなたにアクセスしようとします。

Answer 2

これは私にとってそれを解決したものです。ご協力いただきありがとうございます。

bool sudokuBoard::solvePuzzle() { 
    int row, col; 

    if (emptyCell(row, col) == false) { 
     return true; 
    } 

    for (int i = 1; i < 10; i++) { 
     cout << "Trying " << i << " in spot [" << row << "][" << col << "]" << endl; 
     if (validMove(row, col, i)) { 
      board[row][col] = i; 
      showBoard(); 
      if (solvePuzzle()) { 
       return true; 
      } 
      board[row][col] = 0; 
     } 
    } 
    return false; 
}