Hard
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9 must occur exactly once in each row.
- Each of the digits
1-9 must occur exactly once in each column.
- Each of the the digits
1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.
A sudoku puzzle…
…and its solution numbers marked in red.
Note:
- The given board contain only digits
1-9 and the character '.'.
- You may assume that the given Sudoku puzzle will have a single unique solution.
- The given board size is always
9x9.
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字
1-9 在每一行只能出现一次。
- 数字
1-9 在每一列只能出现一次。
- 数字
1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
一个数独。
答案被标成红色。
Note:
- 给定的数独序列只包含数字
1-9 和字符 '.' 。
- 你可以假设给定的数独只有唯一解。
- 给定数独永远是
9x9 形式的。
想法
这道题想了好久，最后看了网上的答案（sigh），总结了一下，基本就是HashMap+DFS，首先用三个数组存储数独中每一行、每一列、每一个方块中数字的占用情况，然后用回溯法DFS遍历一遍即可。要注意方块的计算公式为$i / 3 \times 3 + j / 3$。写的过程中遇到好多笔误，调了很多遍才能跑通（sigh）。
解
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
| #include <iostream>
#include <cstring>
#include <vector>
using namespace std;
bool row[9][9];
bool column[9][9];
bool box[9][9];
bool done;
void dfs(vector<vector<char> > &board, int i, int j)
{
if (i > 8) {
done = true;
return;
}
if (board[i][j] == '.') {
for (int n = 0; n < 9; n++) {
if (!(row[i][n] || column[j][n] || box[(i / 3) * 3 + j / 3][n])) {
board[i][j] = n + '1';
row[i][n] = column[j][n] = box[(i / 3) * 3 + j / 3][n] = true;
if (j >= 8) {
dfs(board, i + 1, 0);
}
else {
dfs(board, i, j + 1);
}
if (done)
break;
board[i][j] = '.';
row[i][n] = column[j][n] = box[(i / 3) * 3 + j / 3][n] = false;
}
}
}
else {
if (j >= 8) {
dfs(board, i + 1, 0);
}
else {
dfs(board, i, j + 1);
}
}
}
void solveSudoku(vector<vector<char> > &board)
{
memset(row, 0, 9 * 9 * sizeof(bool));
memset(column, 0, 9 * 9 * sizeof(bool));
memset(box, 0, 9 * 9 * sizeof(bool));
done = false;
int num = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
num = board[i][j] - '1';
row[i][num] = true;
column[j][num] = true;
box[(i / 3) * 3 + j / 3][num] = true;
}
}
}
dfs(board, 0, 0);
}
|
