解数独

LeetCode每日一题,37. Sudoku Solver

先看题目描述

大意就是实现一个程序,可以解数独题,解必须满足三个要求:1. 数字 1-9 在每一行只可以出现一次; 2. 数字 1-9 在每一列只可以出现一次; 3. 数字 1-9 在以实线分割的 3*3 方格里只可以出现一次

算法和思路

回溯

使用回溯模拟人的思考方式来解决问题

  • 使用三个布尔数组 rowUsed, colUsed, boxUsed 来记录行列和方格中数字的使用情况,true 表示使用过,false 表示没使用过,例如 rowUsed[0][5] = true,表示第 0 行中,数字 5 已经使用过了;boxUsed[1][0][8] = true,表示第 1 行的第 0 个方格中,数字 8 已经使用过了
  • 在填充数组前先遍历一遍,将三个布尔数组初始化,表明哪些数字已经使用过了
  • 尝试去填充数组,只要行,列, 还有 3*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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public void solveSudoku(char[][] board) {
// 三个布尔数组 表明 行, 列, 还有 3*3 的方格的数字是否被使用过
boolean[][] rowUsed = new boolean[9][10];
boolean[][] colUsed = new boolean[9][10];
boolean[][][] boxUsed = new boolean[3][3][10];
// 初始化三个布尔数组
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[0].length; col++) {
int num = board[row][col] - '0';
if (num >= 1 && num <= 9) {
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[row / 3][col / 3][num] = true;
}
}
}
// 递归尝试填充数组
dfs(0, 0, board, rowUsed, colUsed, boxUsed);
}

private boolean dfs(int row, int col, char[][] board, boolean[][] rowUsed, boolean[][] colUsed, boolean[][][] boxUsed) {
// 边界校验, 如果已经填充完成, 返回true, 表示一切结束
if (col == board[0].length) {
col = 0;
row += 1;
}
if (row == board.length) return true;
// 是空则尝试填充, 否则跳过继续尝试填充下一个位置
if (board[row][col] == '.') {
// 尝试填充1~9
for (int num = 1; num <= 9; num++) {
boolean canUsed = !(rowUsed[row][num] || colUsed[col][num] || boxUsed[row / 3][col / 3][num]);
if (canUsed) {
board[row][col] = (char) (num + '0');
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[row / 3][col / 3][num] = true;
if (dfs(row, col + 1, board, rowUsed, colUsed, boxUsed)) {
return true;
}
board[row][col] = '.';
rowUsed[row][num] = false;
colUsed[col][num] = false;
boxUsed[row / 3][col / 3][num] = false;
}
}
} else {
return dfs(row, col + 1, board, rowUsed, colUsed, boxUsed);
}
return false;
}
}