Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
注意到题目中说的,只要当前已经填充的数字是合法的就可以,不一定要这个数独是有解.（下面说的九宫格都是指3*3的网格）
因此只需要判断9*9网格的每一行、每一列、9个小九宫格是否合法。即如果在每一行、每一列、每个9个小九宫格内，某个数字重复出现了，当前数独就是不合法的。 本文地址
网上很多解法是：行、列、九宫格、分三个两重循环来分别判断是否合法。其实只需要一个两重循环即可
需要注意的是：如果把九宫格按照行从0开始标号，那么数字board[i][j] 位于第 i/3*3+j/3 个九宫格内
|
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
|
class
Solution {
public
:
bool
isValidSudoku(vector<vector<
char
> > &board) {
int
rowValid[10] = {0};
//用于判断某一行是否合法，对于行来说这个数组可以重复使用
int
columnValid[9][10] = {0};
//用于判断某一列是否合法
int
subBoardValid[9][10] = {0};
//用于判断某一个九宫格是否合法
for
(
int
i = 0; i < 9; i++)
{
memset
(rowValid, 0,
sizeof
(rowValid));
for
(
int
j = 0; j < 9; j++)
if
(board[i][j] !=
'.'
)
{
if
(!checkValid(rowValid, board[i][j]-
'0'
) ||
!checkValid(columnValid[j], board[i][j]-
'0'
) ||
!checkValid(subBoardValid[i/3*3+j/3], board[i][j]-
'0'
))
return
false
;
}
}
return
true
;
}
bool
checkValid(
int
vec[],
int
val)
{
if
(vec[val] == 1)
return
false
;
vec[val] = 1;
return
true
;
}
};
|
针对上面的算法，还可以优化空间。上面的算法中，在双重循环时，我们默认了第一重循环表示矩阵的行、第二重循环表示矩阵的列。可以换一种思路：
- 在检测行是否合法时，i 表示矩阵的行，j 表示矩阵的列；
- 检测列是否合法时，i 表示矩阵的列，j 表示矩阵的行；
- 检测九宫格是否合法时，i 表示九宫格的标号，j 表示九宫格里的每个元素（只是我们需要根据i、j定位相应的元素到原来的矩阵：第 i 个九宫格里面的第 j 个元素在原矩阵的第 3*(i/3) + j/3 行，第 3*(i%3) + j%3）列，“/” 表示整数除法）
|
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
|
class
Solution {
public
:
bool
isValidSudoku(vector<vector<
char
> > &board) {
int
rowValid[10] = {0};
//用于判断某一行是否合法
int
columnValid[10] = {0};
//用于判断某一列是否合法
int
subBoardValid[10] = {0};
//用于判断某一个九宫格是否合法
for
(
int
i = 0; i < 9; i++)
{
memset
(rowValid, 0,
sizeof
(rowValid));
memset
(columnValid, 0,
sizeof
(columnValid));
memset
(subBoardValid, 0,
sizeof
(subBoardValid));
for
(
int
j = 0; j < 9; j++)
{
if
(!checkValid(rowValid, board[i][j]-
'0'
) ||
!checkValid(columnValid, board[j][i]-
'0'
) ||
!checkValid(subBoardValid, board[3*(i/3) + j/3][3*(i%3) + j%3]-
'0'
))
return
false
;
}
}
return
true
;
}
bool
checkValid(
int
vec[],
int
val)
{
if
(val < 0)
return
true
;
//对应的是字符‘.’
if
(vec[val] == 1)
return
false
;
vec[val] = 1;
return
true
;
}
};
|
以上的基础上，当然我们还可以用bitmap来更加压缩空间
Sudoku Solver
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.
这种类型的游戏一般回溯法来解决，设置某个空格时，如果该空格无论设置什么数字都无法达到合法状态，那么回溯重新设置上一个空格，详细见代码注释
|
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
|
class
Solution {
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] !=
'.'
)
fill(i, j, board[i][j] -
'0'
);
solver(board, 0);
}
bool
solver(vector<vector<
char
> > &board,
int
index)
{
// 0 <= index <= 80，index表示接下来要填充第index个格子
if
(index > 80)
return
true
;
int
row = index / 9, col = index - 9*row;
if
(board[row][col] !=
'.'
)
return
solver(board, index+1);
for
(
int
val =
'1'
; val <=
'9'
; val++)
//每个为填充的格子有9种可能的填充数字
{
if
(isValid(row, col, val-
'0'
))
{
board[row][col] = val;
fill(row, col, val-
'0'
);
if
(solver(board, index+1))
return
true
;
clear(row, col, val-
'0'
);
}
}
board[row][col] =
'.'
;
//注意别忘了恢复board状态
return
false
;
}
//判断在第row行col列填充数字val后，是否是合法的状态
bool
isValid(
int
row,
int
col,
int
val)
{
if
(rowValid[row][val] == 0 &&
columnValid[col][val] == 0 &&
subBoardValid[row/3*3+col/3][val] == 0)
return
true
;
return
false
;
}
//更新填充状态
void
fill(
int
row,
int
col,
int
val)
{
rowValid[row][val] = 1;
columnValid[col][val] = 1;
subBoardValid[row/3*3+col/3][val] = 1;
}
//清除填充状态
void
clear(
int
row,
int
col,
int
val)
{
rowValid[row][val] = 0;
columnValid[col][val] = 0;
subBoardValid[row/3*3+col/3][val] = 0;
}
private
:
int
rowValid[9][10];
//rowValid[i][j]表示第i行数字j是否已经使用
int
columnValid[9][10];
//columnValid[i][j]表示第i列数字j是否已经使用
int
subBoardValid[9][10];
//subBoardValid[i][j]表示第i个小格子内数字j是否已经使用
};
|
