Desicription
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
A sudoku puzzle…
…and its solution numbers marked in red.
Solution
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
|
class {
private:
bool row[10][10] = {0};
bool col[10][10] = {0};
bool block[10][10] = {0};
bool flag = 0;
public:
void solveSudoku(vector<vector<char>>& board) {
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(board[i][j] == '.')
continue;
int index = i / 3 * 3 + j / 3;
int num = board[i][j] - '0';
row[i][num] = 1;
col[j][num] = 1;
block[index][num] = 1;
}
}
dfs(board, 0, 0);
}
void dfs(vector<vector<char>>& board, int x, int y){
if(flag)
return ;
if(x == 9){
flag = 1;
return ;
}
if(board[x][y] != '.'){
if(y < 8)
dfs(board, x, y+1);
else
dfs(board, x+1, 0);
return ;
}
int index = x / 3 * 3 + y / 3;
for(int num = 1; num <= 9; num++){
if(row[x][num] || col[y][num] || block[index][num])
continue;
row[x][num] = col[y][num] = block[index][num] = 1;
board[x][y] = num + '0';
if(y < 8)
dfs(board, x, y+1);
else
dfs(board, x+1, 0);
if(flag)
return ;
row[x][num] = col[y][num] = block[index][num] = 0;
board[x][y] = '.';
}
}
};
|
近期评论