题目描述

数独是一种传统益智游戏，你需要把一个 $9 \times 9$ 的数独补充完整，使得图中每行、每列、每个 $3 \times 3$ 的九宫格内数字 $1$ ∼ $9$ 均恰好出现一次。

请编写一个程序填写数独。

输入格式

输入共 $9$ 行，每行包含一个长度为 $9$ 的字符串，用来表示数独矩阵。

其中的每个字符都是 $1 ∼ 9$ 或 .（表示尚未填充）。

输出格式

输出补全后的数独矩阵。

数据保证有唯一解。

输入样例：

.2738..1.
.1...6735
.......29
3.5692.8.
.........
.6.1745.3
64.......
9518...7.
.8..6534.

输出样例：

527389416
819426735
436751829
375692184
194538267
268174593
643217958
951843672
782965341

既然是简单版，当然是要爆搜啦~

那么如何搜嘞？
由于数据范围应该不坑
所以可以选择一种最为暴力的搜索方式~

从 $(0, 0)$ 开始，

• 如果当前格为.，那么分别按 行、列、九宫格 判断一下还能填几，然后搜索所有可以填的数
• 如果当前格为数字，直接跳过

那么每层搜索之后呢？

• 如果当前格为最下面那行，那么跳到第一行下一列
• 否则如果当前行并非最后一行，则跳到该列下面那行
• 否则当前行为最后一行，说明填完了，直接返回

虽然暴力的不能再暴力了，但从结果上看，跑得还不错，至少这题过了。

时间复杂度：玄学

代码及注释如下

$C++$ 代码

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 10;
// 由于我是直接用字符数组存数独，以字符串的方式读入，每行后面在读入的时候会被自动加上一个 '\0'，所以数组大小 N 要开到 10，才能避免溢出。

char g[N][N];

bool dfs(int x, int y)
{
    if (y == 9) return true;                  // 如果当前列跳出了最后一列，则直接放回 true
    if (x == 9) return dfs(0, y + 1);         // 如果当前行跳出了最后一行，则返回下一列第㥷行
    if (g[x][y] != '.') return dfs(x + 1, y); // 如果当前行已有数字，直接跳过

    bool st[N];                               // st 数组存当前位置 (x, y) 还能填哪些数
    memset(st, false, sizeof st);             // 要记得初始化~

    for (int i = 0; i < N - 1; i ++ )         // 看一下该列上有哪些数字被填过了
        if (g[i][y] > 47 && g[i][y] < 58)
            st[g[i][y] ^ 48] = true;

    for (int i = 0; i < N - 1; i ++ )         // 看一下该行上有哪些数字被填过了
        if (g[x][i] > 47 && g[x][i] < 58)
            st[g[x][i] ^ 48] = true;

    int sx = x / 3 * 3, sy = y / 3 * 3;       // 找到当前九宫格的左上角位置
    for (int i = sx; i < sx + 3; i ++ )       // 看一下该九宫格内有哪些数字被填过了
        for (int j = sy; j < sy + 3; j ++ )
            if (g[i][j] > 47 && g[i][j] < 58)
                st[g[i][j] ^ 48] = true;

    for (int i = 1; i < N; i ++ )             // 枚举当前格内能填的所有数字
        if (!st[i])
        {
            g[x][y] = i ^ 48;                 // 如果能填，那么填上，并搜索下一格
            if (dfs(x + 1, y)) return true;
        }
    g[x][y] = '.';                            // 如果搜完了所有可填数字，或没有可填数字，那么将该格改为未填状态
    return false;                             // 并返回 false
}

int main()
{
    for (int i = 0; i < N - 1; i ++ )
        scanf("%s", g[i]);                    // 以字符串方式读入

    dfs(0, 0);                                // 从 (0, 0) 开始爆搜

    for (int i = 0; i < N - 1; i ++ , putchar('\n')) // 你们口中奇怪的 for 循环
        for (int j = 0; j < N - 1; j ++ )
            putchar(g[i][j]);                 // 输出填好的数独。由于数据保证有解且有唯一解，所以不需特判任何情况，直接输出即可
    return 0;
}