A37442. 数独填数数独是源自18世纪瑞士的一种数学游戏。玩家需要根据9×9网格上的已知数字，将剩余的所有空格填上数字，使得9×9网格上每一行、每一列及每一个3×3方块（粗线）内的数字均包含1~9，并且数字不重复。例1：下图（左）是未完成的数独，下图（右）是完成后的结果。这个数独可以使用如下9×9的字符方阵表示（空格用“.”表示）：未完成17.5..8...52.1.........759..8...94.…
题目描述
数独填数
数独是源自18世纪瑞士的一种数学游戏。玩家需要根据9×9网格上的已知数字，将剩余的所有空格填上数字，使得9×9网格上每一行、每一列及每一个3×3方块（粗线）内的数字均包含1~9，并且数字不重复。
例1：下图（左）是未完成的数独，下图（右）是完成后的结果。
这个数独可以使用如下9×9的字符方阵表示（空格用“.”表示）：
未完成
17.5..8..
.52.1....
.....759.
.8...94.3
.197.4..8
7......15
4.1...6..
3...2..59
...96..3.
已完成
174593826
952816347
638247591
286159473
519734268
743682915
491375682
367428159
825961734
例2：
未完成
68.9.5...
..3...5.8
4.21.87.3
39.72.8..
.......1.
.45..69..
.6.8.4..2
..1..2.75
7...13...
已完成
687935241
913247568
452168793
396721854
278459316
145386927
569874132
831692475
724513689
例3：
未完成
835.2..41
.2.....39
.4.81....
.869.....
2.1..47..
9.....286
...356..7
.9..4.3..
5....7.1.
已完成
835729641
127465839
649813572
386972154
251684793
974531286
418356927
792148365
563297418
现在给定一道数独题，请编程完成填数，并输出最后的结果。
输入描述
共有9行，表示未完成的数独
每一行包含9个字符（字符只能为1~9的数字和“.”），字符之间没有空格及其他字符
其中“.”表示数独上的空格
题目数据保证数独有效且答案唯一
输出描述
输出9行，表示已完成的数独
每行9个数字，数字之间没有空格及其他字符
样例输入
17.5..8..
.52.1....
.....759.
.8...94.3
.197.4..8
7......15
4.1...6..
3...2..59
...96..3.
样例输出
174593826
952816347
638247591
286159473
519734268
743682915
491375682
367428159
825961734
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 9;
int g[N][N];
int isValid(int r, int c, int x) {
// 同行，同列是不是存在同样的数字x
for (int i = 0; i < 9; i++)
if (g[r][i] == x || g[i][c] == x) return 0;
// 找出3X3的小方块开始行和开始列,也就是所在块左上角坐标
int row = r / 3 * 3;
int col = c / 3 * 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (g[row + i][col + j] == x)
return 0;
return 1;
}
int dfs() {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (g[r][c] == 0) {
for (int x = 1; x <= 9; x++) {
if (isValid(r, c, x)) {
g[r][c] = x;
if (dfs()) return true;
g[r][c] = 0;
}
}
return 0;
}
}
}
return 1;
}
int main() {
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
char x;
cin >> x;
if (x != '.') g[i][j] = x - '0';
}
dfs();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) cout << g[i][j];
cout << endl;
}
return 0;
}