C ++中的递归回溯

Question

我正在尝试编写一个程序，该程序将使用回溯来创建数独求解器。我已经能够创建一个黑色的数独网格，并且可以检查一步棋是否有效。我的程序工作正常，直到有不止一种数字可供选择。

问题：请看一下我的 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|

我的程序在第一行的最后一个 0 停止，因为没有解决方案，除非前面的 4 变为 7，程序终止。

Answer 1

回溯可能很难让您在第一时间全神贯注，因此我们将从您现在拥有的一些伪代码开始逐步进行此操作：

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

一旦由于先前选择的值而无法为正方形找到有效移动，这当然会卡住。

为了解决这个问题，我们需要 return 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
}

现在这被认为是一种蛮力方法，可以进行优化，但是对于你的问题，让回溯工作，如果你愿意，你可以稍后担心速度优化。

请注意我评论的两个重要位置，第一个是表示没有剩余空方块的指示符。由于您的程序只分配有效的移动，拼图在这里应该是完整和正确的，所以程序 return 是正确的。这是基本情况，通常递归函数需要一个基本情况。

第二个重要的一点是函数递归调用自身的位置。请注意，它仍在循环中，因此当调用 returns 为 false 时，它将在之前的调用中恢复循环。除了我们的示例 return 之外，每个调用都会像 this example 中那样堆叠到另一个调用上。

请注意，直到递归函数 returns 之后单元格才会取消分配，这使您不必担心将 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;
}

C ++中的递归回溯

Recursive Backtracking in c++

c++

recursive-backtracking