P1784 数独

题目描述

数独是根据 \(9 \times 9\) 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 \(1 - 9\) ，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。

这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。

据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所有数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。

输入格式

一个未填的数独。

输出格式

填好的数独。

输入输出样例 #1

输入 #1

8 0 0 0 0 0 0 0 0 
0 0 3 6 0 0 0 0 0 
0 7 0 0 9 0 2 0 0 
0 5 0 0 0 7 0 0 0 
0 0 0 0 4 5 7 0 0 
0 0 0 1 0 0 0 3 0 
0 0 1 0 0 0 0 6 8 
0 0 8 5 0 0 0 1 0 
0 9 0 0 0 0 4 0 0

输出 #1

8 1 2 7 5 3 6 4 9 
9 4 3 6 8 2 1 7 5 
6 7 5 4 9 1 2 8 3 
1 5 4 2 3 7 8 9 6 
3 6 9 8 4 5 7 2 1 
2 8 7 1 6 9 5 3 4 
5 2 1 9 7 4 3 6 8 
4 3 8 5 2 6 9 1 7 
7 9 6 3 1 8 4 5 2

说明/提示

2022-04-17 @farteryhr 贡献了三组 hack 数据。加入了其中两组。第三组过强（来源：https://www.dcc.fc.up.pt/~acm/sudoku.pdf），放在下边供自测。

9 0 0 8 0 0 0 0 0
0 0 0 0 0 0 5 0 0 
0 0 0 0 0 0 0 0 0 
0 2 0 0 1 0 0 0 3
0 1 0 0 0 0 0 6 0
0 0 0 4 0 0 0 7 0
7 0 8 6 0 0 0 0 0 
0 0 0 0 3 0 1 0 0 
4 0 0 0 0 0 2 0 0

输出

9 7 2 8 5 3 6 1 4 
1 4 6 2 7 9 5 3 8 
5 8 3 1 4 6 7 2 9 
6 2 4 7 1 8 9 5 3 
8 1 7 3 9 5 4 6 2 
3 5 9 4 6 2 8 7 1 
7 9 8 6 2 1 3 4 5 
2 6 5 9 3 4 1 8 7 
4 3 1 5 8 7 2 9 6

Tip

b站讲解链接

📌 题目分析

给定数据：

一个 9 × 9 的残缺网格
要求每行、每列、每个 3 × 3 粗线宫内的数字 1~9 均不重复

要求推理出所有剩余空格的数字，并输出唯一解。

👉 本质：

多重约束条件下的状态穷举

👉 类型：

经典 回溯法 (Backtracking) / 深度优先搜索 (DFS)

🧠 解题思路

1️⃣ 为什么是回溯法

数独是回溯算法的“教科书级”应用。由于数独有极其严格的规则限制，当我们在一个空格填入数字时，就像是在走迷宫时选择了一个岔路口。 * 如果这个数字填对了，我们就继续往下填下一个空格。 * 如果填到后面发现“死胡同”了（某个空格 1 到 9 全都填不进去），说明我们前面肯定有哪一步选错了。此时就需要退回来（回溯），把之前的数字擦掉，换一个数字重新试。

2️⃣ 核心技巧：O(1) 的快速校验

如果我们每次填数字都要去用 for 循环检查一遍这一行、这一列、这一个九宫格有没有重复数字，程序会跑得很慢。 空间换时间技巧：我们开三个二维布尔数组来当“登记册”： * row[x][i]：表示第 x 行是否已经有了数字 i。 * col[y][i]：表示第 y 列是否已经有了数字 i。 * block[b][i]：表示第 b 个九宫格是否已经有了数字 i。

这样，校验某个数字能不能填，只需要 if (!row[x][i] && !col[y][i] && !block[b][i]) 这一瞬间的判断即可。

3️⃣ 九宫格编号的数学魔法

对于坐标 (x, y)（假设下标从 1 开始到 9），它到底属于哪个 \(3 \times 3\) 的九宫格呢？这是一个极其经典的坐标映射公式。我们将 9×9 分割为 9 个区块，编号 1 到 9，公式如下：

block_id = (x - 1) / 3 * 3 + (y - 1) / 3 + 1

(注：C++ 里的整数除法会自动向下取整，这个公式能完美将坐标映射到 1~9 的宫格编号里。)

4️⃣ 时间复杂度

虽然最坏情况下 DFS 的时间复杂度是 \(O(9^{\text{空白格子数}})\)，但在数独极其严苛的剪枝条件（三重校验）下，绝大多数错误分支会在第一两步就被立刻扼杀。对于 \(9 \times 9\) 的标准数独，这种朴素的 DFS 回溯法能在几毫秒内瞬间秒杀。

💻 C++代码

#include <iostream>
using namespace std;

int a[15][15]; // 数独棋盘
bool row[10][10];   // row[x][i] 记录第 x 行是否用过数字 i
bool col[10][10];   // col[y][i] 记录第 y 列是否用过数字 i
bool block[10][10]; // block[b][i] 记录第 b 个宫是否用过数字 i

// 根据横纵坐标计算属于第几个 3x3 宫格
int get_block(int x, int y) {
    return (x - 1) / 3 * 3 + (y - 1) / 3 + 1;
}

// 打印最终答案
void print_ans() {
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
}

// DFS 回溯填数，返回 bool 代表是否找到了最终解
bool dfs(int x, int y) {
    // 1. 如果 x 走到了 10，说明 1~9 行全部填完，成功！
    if (x == 10) {
        print_ans();
        return true;
    }

    // 2. 如果当前行走到了尽头（y 到了 10），换到下一行的第 1 列继续搜
    if (y == 10) {
        return dfs(x + 1, 1);
    }

    // 3. 如果当前格子已经有数字了，直接跳过，搜下一个格子
    if (a[x][y] != 0) {
        return dfs(x, y + 1);
    }

    // 4. 当前格子是 0，尝试填入 1~9
    int b = get_block(x, y);
    for (int i = 1; i <= 9; i++) {
        // 校验：行、列、宫中都没有用过该数字
        if (!row[x][i] && !col[y][i] && !block[b][i]) {

            // 【保护现场】填入数字，并登记
            a[x][y] = i;
            row[x][i] = true;
            col[y][i] = true;
            block[b][i] = true;

            // 继续往下搜，如果底层的搜索返回 true，说明整个数独解完了，一路向上传递结束信号
            if (dfs(x, y + 1)) {
                return true;
            }

            // 【恢复现场 / 回溯】底层的路走不通，撤销当前的操作，换下一个数字试
            a[x][y] = 0;
            row[x][i] = false;
            col[y][i] = false;
            block[b][i] = false;
        }
    }

    // 1~9 都试了还是不行，说明上一步填错了，返回 false 让上一步回溯
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            cin >> a[i][j];
            if (a[i][j] != 0) {
                int val = a[i][j];
                row[i][val] = true;
                col[j][val] = true;
                block[get_block(i, j)][val] = true;
            }
        }
    }

    // 从坐标 (1, 1) 开始搜索
    dfs(1, 1);

    return 0;
}

⚠️ 易错点

❌ 1. 返回值设计缺陷导致输出乱码

很多人在写 dfs(x, y) 时习惯用 void 类型。当走到 x == 10 时打印数组然后 return;。 致命失误：数独只需要输出一个正确解。如果不用 bool 类型层层向上阻断，程序在输出正确答案后，会继续往后回溯，又把正确的数字擦掉去尝试别的组合，甚至输出多个错乱的棋盘。利用 if(dfs(...)) return true; 这一招可以实现“找到就立刻强制全剧终”的效果。

❌ 2. 忘记初始化原始数据

读取棋盘数据时，对于非 0 的已知数字，必须立刻在对应的 row, col, block 数组中打上 true 的标记！ 如果漏了这一步，系统会认为 1~9 都还没填过，导致原有的数字在同一行被重复填入。

❌ 3. 宫格数组索引越界或重叠

如果你不用 1 到 9，而是混合使用 0 到 8 来计算坐标，特别容易在 b = (x/3)*3 + (y/3) 这种地方搞错。统一让所有的坐标、数字、宫格都保持在 1 ~ 9 的闭区间，是避免下标越界和调试痛苦的最佳实践。

🚀 一句话总结

数独破解术 = DFS + 行列宫的 O(1) 状态本，填字失败就擦除退回，一路直达第 10 行即是胜利。

🔥 补充：硬核知识点

进阶：Dancing Links (舞蹈链 / DLX) 算法

虽然普通的 DFS 回溯可以秒杀 \(9 \times 9\) 数独，但如果你面对的是变态级的 \(16 \times 16\) 甚至 \(25 \times 25\) 的超大数独（例如洛谷上的高阶靶场题），普通 DFS 会直接超时到天荒地老。

这时候，计算机科学巨擘、图灵奖得主 Donald Knuth（高德纳） 提出了一个极其优美的数据结构：十字交叉双向循环链表 (Dancing Links)。

降维打击原理：DLX 将数独问题巧妙地转换为了图论中经典的“精确覆盖问题 (Exact Cover)”。它把行、列、宫、格的约束转化为一个极大的稀疏 01 矩阵，每一行代表一个“在 (x,y) 填入数字 v”的动作，每一列代表一个约束。
舞蹈般的回溯：在回溯时，利用链表删除和恢复节点只需改变一下前后指针的指向，时间复杂度为绝对的 \(O(1)\)： L[R[c]] = c; R[L[c]] = c; 指针解开又缝合的过程就像在跳舞一样优雅，因此被命名为“舞蹈链”。它是目前人类已知的解决数独及各类拼图游戏最快、最强悍的终极算法！