在C++中的遞歸回溯

Question

我想寫一個程序，將使用回溯來創建一個數獨求解器。我已經能夠創建一個黑色的數獨網格，我可以檢查一下是否有效的舉動。我的程序工作正常，直到有一個正方形的數字不止一個選擇。

問題：你會看看我的解決方法，看看我如何修改它來回溯，改變答案並再次前進。我列出了上述所有其他方法的名稱以及所有這些工作。

示例輸入：

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| 

我的程序在所述第一行的最後一個0停止，因爲沒有解決方案，除非該前4個變化爲7，該程序終止。

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 
} 

現在，這被認爲是暴力破解的方法，可以優化，但你的問題讓我們得到回溯工作，如果你願意，你可以擔心後面的速度優化。

請注意我評論爲重要位的兩個地方，第一個是可以指示沒有空白方格的位置。由於你的程序只分配有效的移動，所以這裏的謎題應該完整且正確，所以程序返回true。這是基本情況，通常遞歸函數需要基本情況​​。

第二個重要位是函數遞歸調用自身的位置。請注意它仍在循環中，所以當一個調用返回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; 
}