2

我正在尝试编写一个程序，该程序将使用回溯来创建数独求解器。我已经能够创建一个黑色数独网格，我可以检查一个动作是否是有效的动作。我的程序运行良好，直到一个正方形有多个数字可供选择。

问题：你会看看我的 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，否则程序终止。

4

2 回答 2

4

第一次回溯可能很难让您完全理解，因此我们将从您现在所拥有的一些伪代码开始逐步进行此操作：

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

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

为了解决这个问题，false当我们用完方格中的有效移动时，我们需要返回，我们还需要取消分配我们的猜测以使方格再次为空。然后我们需要在我们离开的前一个方块中恢复循环。

所以我们的 find valid move 函数（在你的情况下解决难题）可能看起来像这样：

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 时，它​​将在前一个调用中恢复循环。除了我们的示例返回到循环之外，每个调用都像本示例中一样堆叠到另一个调用上。

请注意，在递归函数返回之前，单元格不会被取消分配，这使您不必担心将 1 添加到您在评论中提到的行和列。您所要做的就是拥有一个可靠的 findEmptySquare 方法，然后递归处理剩下的事情。

你的showBoard();方法对于调试来说是无价的，我会说把它放在后面assignMoveToSquare

希望这会有所帮助，你真的很亲密，所以我认为它会的。如果您还有其他问题，请随时对此发表评论，我会在有时间时尝试与您联系。

于 2017-03-16T15:44:01.787 回答
0

这就是为我解决的问题。谢谢你的帮助。

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;
}
于 2017-03-17T04:31:18.577 回答