题解：B4279 [蓝桥杯青少年组国赛 2023] 数独填数
思路与算法
题目大意
题目给定一个未完成的数独（用 . 表示空格），保证有唯一解，要求输出填完后的数独。
忘记数独规则的~和不会玩数独的~看过来：
数独需要玩家在一个 \(9 \times 9\) 的网格中填入数字 \(1 \sim 9\)，使得：
- 每一行包含 \(1 \sim 9\) 且不重复；
- 每一列包含 \(1 \sim 9\) 且不重复；
- 每一个 \(3 \times 3\) 的格子包含 \(1 \sim 9\) 且不重复。
算法
注意到，算法标签说明这是一道 DFS 题，
这里我们可以使用 DFS 遍历并枚举每一个空格所填的数，并检查是否合法。
所以，这里我们用的算法就会是 DFS（深度优先搜索）啦，也就变成了一道橙题。
代码
C/C++：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70 | #include <stdio.h>
#include <stdbool.h>
char board[9][9];
bool solved = false;
bool isValid(int row, int col, char num) {
for (int i = 0; i < 9; i++) {
if (board[row][i] == num) {
return false;
}
}
for (int i = 0; i < 9; i++) {
if (board[i][col] == num) {
return false;
}
}
int boxRow = row / 3 * 3;
int boxCol = col / 3 * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[boxRow + i][boxCol + j] == num) {
return false;
}
}
}
return true;
}
void dfs(int row, int col) {
if (row == 9) {
solved = true;
return;
}
if (col == 9) {
dfs(row + 1, 0);
return;
}
if (board[row][col] != '.') {
dfs(row, col + 1);
return;
}
for (char num = '1'; num <= '9'; num++) {
if (isValid(row, col, num)) {
board[row][col] = num;
dfs(row, col + 1);
if (solved) {
return;
}
board[row][col] = '.';
}
}
}
int main() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
scanf("%c", &board[i][j]);
}
getchar(); // 吃换行
}
dfs(0, 0);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
printf("%c", board[i][j]);
}
printf("\n");
}
return 0;
}
|