回溯算法——LeetCode37 解数独

题目

力扣题目链接

思路

1. 卡哥的思路，注意看他解释为什么是“二维回溯”。
2. 我的思路，类似y总解决 N 皇后问题时的第二种方法，即从左上到右下枚举棋盘的每个位置。
   至于为什么与 N 皇后问题不一样，我认为是因为它每一行不止放一个，每一行的每个位置都要进行考虑。

代码

1. 卡哥代码见上方思路。
2. 我的代码：

class Solution {
private:bool isValid(int row, int col, char val, vector<vector<char>>& board) {// 判断该行是否有重复for (int i = 0; i < 9; i++) {if (board[row][i] == val) {return false;}}// 判断该列是否有重复for (int i = 0; i < 9; i++) {if (board[i][col] == val) {return false;}}// 判断九宫格内是否有重复// 很巧妙int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) {for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val) {return false;}}}return true;}// 有返回值是因为只需要找到一种可行的方案，好好理解一下bool backtracking(int x, int y, vector<vector<char>>& board) {// 遍历到一行的末尾了，就开始遍历下一行if (y == 9) {y = 0;x++;}// x == 9说明 0~8 这9行都遍历完了if (x == 9) {return true;}// 如果该位置还没填数的if (board[x][y] == '.') {// 遍历9种可能for (char i = '1'; i <= '9'; i++) {if (isValid(x, y, i, board)) {board[x][y] = i;if (backtracking(x, y + 1, board)) {return true;}board[x][y] = '.';}}// 9种都不行，就返回falsereturn false;}else {return backtracking(x, y + 1, board);}}public:void solveSudoku(vector<vector<char>>& board) {backtracking(0, 0, board);}
};

对于回溯函数为什么需要返回值的解释

ChatGPT：

你原来的代码（返回值为void）在找到一个解之后，会继续尝试其他可能的填充选项，并继续回溯，这样会导致找到的解可能会被覆盖，从而使最终输出的可能不是第一个找到的解，甚至可能无法正确地保留一个有效解。

详细分析

1. 回溯的本质：

   • 你的回溯算法会从左上角开始遍历整个数独网格。如果在某个位置找到了一个有效的填充数字，算法会继续前进，直到填满整个网格，或者无法找到合适的数字为止。
   • 如果算法到达了一个无法继续的状态（即当前路径不再可行），它会回退到上一个状态并尝试其他可能的数字。

2. 没有提前终止：

   • 你的代码中没有检测到第一个有效解后提前终止的机制。
   • 当回溯算法在最后一格填上数字时，虽然它找到了一个有效解，但是它不会立即返回，而是继续尝试回溯，试图寻找其他可能的解。
   • 由于继续回溯，它可能会更改已经填好的数字，尝试其他路径，结果导致解被覆盖，或者递归无限循环而导致栈溢出（如你之前遇到的无限递归问题）。

3. 覆盖问题：

   • 在回溯过程中，每当你在一个位置填入一个数字后，都会立即调用递归函数进入下一步。
   • 如果在某个位置找到的第一个有效数字满足所有条件，继续前进，最后递归完成一整次操作后，如果继续回溯，这个数字可能会被回溯掉，并试图用下一个数字替换。
   • 因为没有及时终止，算法会尝试其他可能的数字组合，可能覆盖掉第一个找到的有效解。

解决方法

为了避免上述问题，关键在于：找到第一个有效解后立即终止进一步的回溯和搜索。这可以通过让递归函数在找到一个有效解时返回true来实现，以阻止后续的任何修改。