题目

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：board = [["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]] 输出： [["5","3","4","6","7","8","9","1","2"], ["6","7","2","1","9","5","3","4","8"] ["1","9","8","3","4","2","5","6","7"], ["8","5","9","7","6","1","4","2","3"], ["4","2","6","8","5","3","7","9","1"], ["7","1","3","9","2","4","8","5","6"], ["9","6","1","5","3","7","2","8","4"], ["2","8","7","4","1","9","6","3","5"], ["3","4","5","2","8","6","1","7","9"]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

解题思路

这道题是一个典型的 约束满足问题 (Constraint Satisfaction Problem)，最适合使用 回溯算法 (Backtracking) 来解决。

想象一下我们手动填写数独的过程：

找到一个空格。
从 1 到 9 尝试填入一个数字。
检查这个数字是否符合数独的规则（当前行、列、3x3宫内没有重复）。
如果符合规则：我们就暂时把这个数字放在这里，然后继续去解决下一个空格（重复步骤1-3）。
如果不符合规则：我们就换一个数字再试。
如果 1-9 都试完了都不行，或者我们填完这个数字后，导致后面的某个空格怎么都填不了了，这说明我们当前这一步的数字填错了。怎么办？我们就要 退回 (Backtrack) 到上一个格子，把它擦掉，然后换一个数字再试。

这个“尝试-深入-不行就退回”的过程，就是回溯算法的核心思想。它本质上是一种深度优先搜索（DFS）的暴力枚举，但节约时间之处在于“剪枝”，一旦发现当前的选择不满足约束条件，就不会再继续深入下去，而是直接返回，从而避免了大量无效的搜索。

具体步骤

我们可以把上述思路转换成一个递归程序。

创建一个递归函数，我们称之为 backtrack() 或者 solve()。这个函数的目标是填充数独。
确定递归的终止条件（Base Case）：
- 当我们在棋盘上从头到尾都找不到任何一个空格（.）时，说明整个数独已经被成功填满了。这时，我们找到了一个解，递归结束，返回 true。
开始递归过程：
- 从上到下，从左到右，遍历整个数独棋盘，找到第一个空格 (row, col)。
- 一旦找到这个空格，就开始我们的“尝试”过程：
  - 用一个循环，从数字 1 到 9 进行尝试。
  - 对于每一个尝试的数字 num，我们需要检查其有效性。也就是说，判断把 num 放在 (row, col) 这个位置是否违反数独规则。
    - 检查 (row, col) 所在的行是否已经存在 num。
    - 检查 (row, col) 所在的列是否已经存在 num。
    - 检查 (row, col) 所在的 3x3 小宫格是否已经存在 num。
  - 如果 num 是有效的：
    - a. 将这个数字填入棋盘：board[row][col] = num。
    - b. 调用递归函数 backtrack()，让它去解决棋盘上剩下的空格。
    - c. 如果递归调用返回 true，说明基于当前的选择，后续的空格也都被成功填满了。这意味着我们找到了解，那么就直接返回 true，将这个好消息层层传递回去。
  - 如果 num 无效，或者基于 num 的递归调用返回了 false (说明把 num 放在这里会导致后续无解)： a. 这说明数字 num 不是正确的选择。我们需要撤销这个选择，把当前格子恢复原样，这个过程就是回溯。 b. board[row][col] = '.'。 c. 然后循环继续，尝试下一个数字 (比如 num+1)。
处理无解情况：
- 如果从 1 到 9 的所有数字都尝试完毕，都无法让后续的递归调用成功返回 true，那就说明当前这个空格无论填什么都无法得到解。这意味着之前的某一步填错了。
- 此时，函数应该返回 false，通知上一层的递归调用更换数字。

具体代码

class Solution {
private:
    // 使用布尔数组作为哈希表，空间换时间
    // rows[i][num] 表示第 i 行是否已存在数字 num+1
    vector<vector<bool>> rows;
    // cols[j][num] 表示第 j 列是否已存在数字 num+1
    vector<vector<bool>> cols;
    // boxes[k][num] 表示第 k 个 3x3 宫格是否已存在数字 num+1
    vector<vector<bool>> boxes;

    // 回溯辅助函数
    bool backtrack(vector<vector<char>>& board, int row, int col) {
        // 如果当前行已经超出边界 (row == 9), 说明所有格子都已成功填满
        if (row == 9) {
            return true;
        }

        // 计算下一个要处理的格子的坐标
        int next_row = (col == 8) ? row + 1 : row;
        int next_col = (col == 8) ? 0 : col + 1;

        // 如果当前格子已经有数字，则直接跳到下一个格子
        if (board[row][col] != '.') {
            return backtrack(board, next_row, next_col);
        }

        // 遍历 1-9，尝试填入当前空格
        for (int num = 1; num <= 9; ++num) {
            // 计算当前格子所属的 3x3 宫格的索引
            int box_index = (row / 3) * 3 + (col / 3);

            // 使用哈希表进行 O(1) 复杂度的有效性检查
            // 注意：我们的布尔数组索引是 0-8，对应数字 1-9，所以用 num-1
            if (!rows[row][num - 1] && !cols[col][num - 1] && !boxes[box_index][num - 1]) {
                
                // 1. 做出选择
                board[row][col] = num + '0'; // 将数字转换为字符
                rows[row][num - 1] = true;
                cols[col][num - 1] = true;
                boxes[box_index][num - 1] = true;

                // 2. 继续递归，尝试填充下一个格子
                if (backtrack(board, next_row, next_col)) {
                    return true; // 如果找到了解，直接返回
                }

                // 3. 撤销选择 (回溯)
                // 如果后续路径无解，则恢复当前格子的状态
                board[row][col] = '.';
                rows[row][num - 1] = false;
                cols[col][num - 1] = false;
                boxes[box_index][num - 1] = false;
            }
        }

        // 如果 1-9 都尝试过仍然无解，说明之前的选择有误，返回 false
        return false;
    }

public:
    void solveSudoku(vector<vector<char>>& board) {
        // 初始化哈希表
        rows = vector<vector<bool>>(9, vector<bool>(9, false));
        cols = vector<vector<bool>>(9, vector<bool>(9, false));
        boxes = vector<vector<bool>>(9, vector<bool>(9, false));
        
        // 预处理，将棋盘上已有的数字记录到哈希表中
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    int box_index = (i / 3) * 3 + (j / 3);
                    rows[i][num - 1] = true;
                    cols[j][num - 1] = true;
                    boxes[box_index][num - 1] = true;
                }
            }
        }
        
        // 从 (0, 0) 开始启动回溯
        backtrack(board, 0, 0);
    }
};

37. 解数独

beautifulremi

题目

解题思路

具体步骤

具体代码