36. 有效的数独 Valid Sudoku
题目
请你判断一个 9 x 9 的数独是否有效。
只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
-
数字 1-9 在每一行只能出现一次。
-
数字 1-9 在每一列只能出现一次。
-
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ’.’ 表示。
示例
示例 1：
[plaintext]
1
2
3
4
5
6
7
8
9
10
11
12输入：board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true
示例 2：
[plaintext]
1
2
3
4
5
6
7
8
9
10
11
12
13
14输入：board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 ‘.’
思路
其实就是验证满足上面的 3 个条件：
1）每一行
2）每一列
3）每一个小正方体
java 实现
[java]
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146 public boolean isValidSudoku(char[][] board) {
//1. 每一行
for(int i = 0; i < 9; i++) {
char[] row = board[i];
if(!isValid(row)) {
return false;
}
}
//2. 每一列
for(int i = 0; i < 9; i++) {
char[] columns = getColumns(board, i);
if(!isValid(columns)) {
return false;
}
}
//3. 每一个小的 9 宫格
for(int i = 0; i < 9; i++) {
char[] box = getSubBox(board, i);
if(!isValid(box)) {
return false;
}
}
return true;
}
/**
* 获取小9宫格
*
* 规律：
*
* 0 00 01 02
* 10 11 12
* 20 21 22
*
* 2 （第二行，第一个九宫格）
*
* 根据 index 获取对应的行+列信息
*
* row: 0 1 2
* 3 4 5
* 6 7 8
*
* @param board
* @param index
* @return
*/
private char[] getSubBox(char[][] board, int index) {
char[] box = new char[9];
int size = 0;
int rowNum = index/3;
int columnNum = index%3;
for(int i = rowNum*3; i < rowNum*3+3; i++) {
for(int j = columnNum*3; j < columnNum*3+3; j++) {
box[size++] = board[i][j];
}
}
return box;
}
/**
* 获取指定的列
* @param board
* @param columnIndex
* @return
*/
private char[] getColumns(char[][] board, int columnIndex) {
char[] columns = new char[9];
int size = 0;
for(int i = 0; i < 9; i++) {
char[] rows = board[i];
columns[size++] = rows[columnIndex];
}
return columns;
}
/**
* 只能包含：. 1-9
*
* 不能重复 主要是这个
* @param chars
* @return
*/
private boolean isValid(char[] chars) {
char[] nums = new char[9];
int numSize = 0;
for(char c : chars) {
if(!isValidChar(c)) {
return false;
}
// 忽略处理 .
if('.' == c) {
continue;
}
// 数据重复
if(contains(nums, c)) {
return false;
}
nums[numSize++] = c;
}
// 合法
return true;
}
/**
* 合法的值：. 或者 1-9
* @param c
* @return
*/
private boolean isValidChar(char c) {
if('.' == c) {
return true;
}
if('1' <= c && c <= '9') {
return true;
}
return false;
}
/**
* 是否包含
* @param chars
* @param target
* @return
*/
private boolean contains(char[] chars, char target) {
for(char c : chars) {
if(target == c) {
return true;
}
}
return false;
}
37. 解数独
题目
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ’.’ 表示。
例子
示例 1：
[plaintext]
1
2
3输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 ‘.’
题目数据 保证 输入数独仅有一个解
V1-基本回溯版本
思路
我们可以遍历 [i,j] 位置，如果位置为 ‘.’，在位置上尝试添加 1-9 的数字，然后判断是否合法(T36 解法)。
如果合法，则递归判断是否为已解决。
如果已解决，则直接返回结果；如果没有，则回溯。
java 实现
[java]
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 /**
* 基本思路：
*
* 1. 这一题应该需要回溯？
*
* 2. i,j 位置的元素。首先通过 行、列、小九宫格，来把一个位置可行的元素过滤出来，放在 set 中。
*
* 3. 尝试在这个位置放入一个元素，然后依次放剩下的。如果可以，则可行，如果不行，则回溯重来。
*
* 3.1 完成的条件。放入的元素个数，刚好等于初始 . 的个数
* @param board 棋盘
*/
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0)
return;
solve(board);
}
public boolean solve(char[][] board){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == '.'){
for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9
if(isValid(board, i, j, c)){
board[i][j] = c; //Put c for this cell
if(solve(board))
return true; //If it's the solution return true
else
board[i][j] = '.'; //Otherwise go back
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char c){
for(int i = 0; i < 9; i++) {
if(board[i][col] != '.' && board[i][col] == c) return false; //check row
if(board[row][i] != '.' && board[row][i] == c) return false; //check column
if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
}
return true;
}
效果
这种比较暴力，性能也会差一些。
TC: 20ms, 27.43%
MC: 401MB, 35.96%
V2-回溯版本优化
思路
我们可以通过数组模拟 isValid 方法，提升一下效率。
定义 3 个二维数组，根据 board 初始化数组。
[java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14boolean[][] rowUsed = new boolean[9][10];
boolean[][] colUsed = new boolean[9][10];
boolean[][][] boxUsed = new boolean[3][3][10];
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(board[i][j] != '.') {
int num = (int)(board[i][j] - '0');
rowUsed[i][num] = true;
colUsed[j][num] = true;
boxUsed[i/3][j/3][num] = true;
}
}
}
然后直接回溯使用：
[java]
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 boolean backtracking(int row, int col) {
// 列到达末尾，则换下一行进行处理。
if(col == board[0].length) {
col = 0;
row++;
// 最后结束，终止条件
if(row == board.length) {
return true;
}
}
// 待填入的位置
if(board[row][col] == '.') {
// 尝试 9 种数字
for(int i = 1; i <= 9; i++) {
boolean canUse = !(rowUsed[row][i] || colUsed[col][i] || boxUsed[row/3][col/3][i]);
// 在每行、列、小9宫格可以填写的数字。
if(canUse) {
// 使用
board[row][col] = (char)(i + '0');
rowUsed[row][i] = true;
colUsed[col][i] = true;
boxUsed[row/3][col/3][i] = true;
// 回溯
if(backtracking(row, col + 1)) {
return true;
}
// 清空
board[row][col] = '.';
rowUsed[row][i] = false;
colUsed[col][i] = false;
boxUsed[row/3][col/3][i] = false;
}
}
} else {
// 继续下一列
return backtracking(row, col + 1);
}
return false;
}
效果
TC: 3ms, 96.67%
MC: 40mb, 42.8%
这个使用数组替代方法的好处是，很多数据可以复用，而不是每次都要从头开始计算。
小结
针对数独的合法性校验，本身并不难。
数独解法，在数独的合法性基础之上。一般需要逐个尝试的问题，都可以采用回溯来解决。
有时候使用数组等进行预处理，可以进一步提升算法的效率。
希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。
各位极客的点赞收藏转发，是老马持续写作的最大动力！
开源地址
为了便于大家学习，所有实现均已开源。欢迎 fork + star~
参考资料
https://leetcode.com/problems/valid-sudoku/
https://leetcode.cn/problems/sudoku-solver/
