跳到主要内容

LeetCode 37. 解数独

本节目标

同步维护行、列、宫约束，用回溯原地恢复一个合法数独。

这道题是搜索与剪枝综合中的约束满足问题：每个空格有若干候选数字，但一次填写会同时改变所在行、列和九宫格的后续选择。

查看 LeetCode 原题

题意与约束​

给定一个 9 × 9 棋盘，数字字符表示已知项，. 表示空格。需要原地填满棋盘，使每行、每列以及每个 3 × 3 宫都恰好包含数字 1 到 9。题目保证输入存在唯一解。

核心函数只接收已经构造好的棋盘，并直接修改它，不负责输入输出。

朴素思路与瓶颈​

最直接的方法是在每个空格尝试 9 个数字，并在每次尝试时扫描整行、整列和所在宫判断是否合法。回溯框架虽然正确，但同一份约束会被重复扫描许多次。

更关键的是：棋盘写入、合法性记录和撤销操作必须保持同步。只修改棋盘而遗漏某一类约束，会使后续分支基于错误状态继续搜索。

三张占用表​

预处理三个集合：

  • rows[row]：第 row 行已经出现的数字；
  • cols[col]：第 col 列已经出现的数字；
  • boxes[row / 3 * 3 + col / 3]：所在九宫格已经出现的数字。

同时按固定顺序收集所有空格。递归参数 index 表示接下来填写第几个空格；当 index 等于空格数量时，所有约束均已满足，找到可行解。

尝试数字时，只要它出现在任一占用表中就跳过。合法选择要执行四件事：写入棋盘，登记行，登记列，登记宫。若后续失败，再以相反顺序完整撤销这四项修改。

由于题目只要求一个解，递归函数返回布尔值。一旦后续成功，就沿调用栈立即返回，不再恢复成功路径。

代码实现​

C++ 使用固定大小的布尔数组，Python 使用集合。两种实现都保留平台要求的 solveSudoku 方法名，内部回溯函数命名为 backtrack。

C++17
#include <array>
#include <utility>
#include <vector>

using namespace std;

class Solution {
private:
    array<array<bool, 10>, 9> rows{};
    array<array<bool, 10>, 9> cols{};
    array<array<bool, 10>, 9> boxes{};
    vector<pair<int, int>> blanks;

    int boxIndex(int row, int col) const {
        return row / 3 * 3 + col / 3;
    }

    bool backtrack(vector<vector<char>>& board, int index) {
        if (index == static_cast<int>(blanks.size())) {
            return true;
        }

        const auto [row, col] = blanks[index];
        const int box = boxIndex(row, col);
        for (int digit = 1; digit <= 9; digit++) {
            if (rows[row][digit] || cols[col][digit] || boxes[box][digit]) {
                continue;
            }

            board[row][col] = static_cast<char>('0' + digit);
            rows[row][digit] = true;
            cols[col][digit] = true;
            boxes[box][digit] = true;

            if (backtrack(board, index + 1)) {
                return true;
            }

            board[row][col] = '.';
            rows[row][digit] = false;
            cols[col][digit] = false;
            boxes[box][digit] = false;
        }

        return false;
    }

public:
    void solveSudoku(vector<vector<char>>& board) {
        rows = {};
        cols = {};
        boxes = {};
        blanks.clear();

        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.') {
                    blanks.push_back({row, col});
                    continue;
                }
                const int digit = board[row][col] - '0';
                rows[row][digit] = true;
                cols[col][digit] = true;
                boxes[boxIndex(row, col)][digit] = true;
            }
        }

        backtrack(board, 0);
    }
};

复杂度分析​

设初始有 E 个空格。

  • 粗略上界为每个空格尝试 9 个数字，即 O(9^E)；行、列、宫约束会在实际运行中大量剪枝。
  • 三类占用表大小固定，额外递归栈与空格列表为 O(E)。

易错点​

  • 九宫格编号写错；常用公式是 row / 3 * 3 + col / 3。
  • 写入棋盘后只更新行和列，遗漏九宫格。
  • 回溯失败时没有把棋盘恢复为 .，或没有同步删除占用标记。
  • 找到解后仍继续搜索，导致成功路径被后续撤销。
  • 另写一个读取输入的入口，破坏平台原地修改接口。

模式迁移​

数独代表一类“变量 + 候选值 + 多组约束”的问题。字符填格、排课和小规模约束分配都可以用占用表把重复合法性检查变成常数时间。若还需要优化，可以优先选择候选最少的空格；精确覆盖等方法则留给进阶内容。