来源Leetcode第37题解数独
回溯法
现在准备好写回溯函数了
backtrack(row = 0, col = 0)。
从最左上角的方格开始 row = 0, col = 0。直到到达一个空方格。
从1 到 9 迭代循环数组，尝试放置数字 d 进入 (row, col) 的格子。
如果数字 d 还没有出现在当前行，列和子方块中：
将 d 放入 (row, col) 格子中。
- 记录下 d 已经出现在当前行，列和子方块中。
- 如果这是最后一个格子row == 8, col == 8 ：
- 意味着已经找出了数独的解。
- 否则
- 放置接下来的数字。
- 如果数独的解还没找到：将最后的数从 (row, col) 移除。
代码如下：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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163 // box size
int n = 3;
// row size
int N = n * n;
int [][] rows = new int[N][N + 1];
int [][] columns = new int[N][N + 1];
int [][] boxes = new int[N][N + 1];
char[][] board;
boolean sudokuSolved = false;
public boolean couldPlace(int d, int row, int col) {
/*
Check if one could place a number d in (row, col) cell
*/
int idx = (row / n ) * n + col / n;
return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
}
public void placeNumber(int d, int row, int col) {
/*
Place a number d in (row, col) cell
*/
int idx = (row / n ) * n + col / n;
rows[row][d]++;
columns[col][d]++;
boxes[idx][d]++;
board[row][col] = (char)(d + '0');
}
public void removeNumber(int d, int row, int col) {
/*
Remove a number which didn't lead to a solution
*/
int idx = (row / n ) * n + col / n;
rows[row][d]--;
columns[col][d]--;
boxes[idx][d]--;
board[row][col] = '.';
}
public void placeNextNumbers(int row, int col) {
/*
Call backtrack function in recursion
to continue to place numbers
till the moment we have a solution
*/
// if we're in the last cell
// that means we have the solution
if ((col == N - 1) && (row == N - 1)) {
sudokuSolved = true;
}
// if not yet
else {
// if we're in the end of the row
// go to the next row
if (col == N - 1) backtrack(row + 1, 0);
// go to the next column
else backtrack(row, col + 1);
}
}
public void backtrack(int row, int col) {
/*
Backtracking
*/
// if the cell is empty
if (board[row][col] == '.') {
// iterate over all numbers from 1 to 9
for (int d = 1; d < 10; d++) {
if (couldPlace(d, row, col)) {
placeNumber(d, row, col);
placeNextNumbers(row, col);
// if sudoku is solved, there is no need to backtrack
// since the single unique solution is promised
if (!sudokuSolved) removeNumber(d, row, col);
}
}
}
else placeNextNumbers(row, col);
}
public void solveSudoku(char[][] board) {
this.board = board;
// init rows, columns and boxes
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
char num = board[i][j];
if (num != '.') {
int d = Character.getNumericValue(num);
placeNumber(d, i, j);
}
}
}
backtrack(0, 0);
}
//Type 2
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(1 <= num && num <= 9){
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[row/3][col/3][num] = true;
}
}
}
// 递归尝试填充数组
recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, 0, 0);
}
private boolean recusiveSolveSudoku(char[][]board, boolean[][]rowUsed, boolean[][]colUsed, boolean[][][]boxUsed, int row, int col){
// 边界校验, 如果已经填充完成, 返回true, 表示一切结束
if(col == board[0].length){
col = 0;
row++;
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){
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[row/3][col/3][num] = true;
board[row][col] = (char)('0' + num);
if(recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1)){
return true;
}
//填充失败，那么我们需要回溯。将原来尝试填充的地方改回来。
board[row][col] = '.';
rowUsed[row][num] = false;
colUsed[col][num] = false;
boxUsed[row/3][col/3][num] = false;
}
}
} else {
return recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1);
}
return false;
}
剪枝
搜索+剪枝的方法其实是有在上学期的课设时做了的，但是emm完全忘了，挖个坑，有空填了
代码如下：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/*
剪枝条件:我们应该选择的格子（'.'）在一行、一列和一个九宫格中可选数字最少的格子开始填数字。
对于每行、每列和每个9宫格都可以用一个9位的2进制数字来标识该行（列，9宫格）那些数字可以填。
用1表示可填0表示不可填
如例题中第一行 ：["5","3",".",".","7",".",".",".","."]
第一行中 有数字 5 3 7
下标 8 7 6 5 4 3 2 1 0
二进制数 0 0 1 0 1 0 1 0 0
一共有9行所以用9个int表示行row[9],同理9列col[9],9个9宫格cell[3][3]*/
class Solution {
final int N = 9;
int[] row = new int [N], col = new int [N];
//ones数组表示0~2^9 - 1的整数中二进制表示中1的个数:如ones[7] = 3 ones[8] = 1
//map数组表示2的整数次幂中二进制1所在位置（从0开始） 如 map[1] = 0,map[2] = 1, map[4] = 2
int[] ones = new int[1 << N], map = new int[1 << N];
int[][] cell = new int[3][3];
public void solveSudoku(char[][] board) {
init();
int cnt = fill_state(board);
dfs(cnt, board);
}
void init(){
for(int i = 0; i < N; i++) row[i] = col[i] = (1 << N) - 1;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
cell[i][j] = (1 << N) - 1;
//以上2个循环把数组的数初始化为二进制表示8个1，即一开始所以格子都可填
for(int i = 0; i < N; i++) map[1 << i] = i;
//统计0~2^9 - 1的整数中二进制表示中1的个数
for(int i = 0; i < 1 << N; i++){
int n = 0;
for(int j = i; j != 0; j ^= lowBit(j)) n++;
ones[i] = n;
}
}
int fill_state(char[][] board){
int cnt = 0; //统计board数组空格('.')的个数
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(board[i][j] != '.'){
int t = board[i][j] - '1';
//数独中 i,j位置为数组，修改row col cell数组中状态
change_state(i, j, t);
}else cnt++;
}
}
return cnt;
}
boolean dfs(int cnt, char[][] board){
if(cnt == 0) return true;
int min = 10, x = 0, y = 0;
//剪枝，即找出当前所以空格可填数字个数最少的位置 记为x y
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(board[i][j] == '.'){
int k = ones[get(i, j)];
if(k < min){
min = k;
x = i;
y = j;
}
}
}
}
//遍历当前 x y所以可选数字
for(int i = get(x, y); i != 0; i ^= lowBit(i)){
int t = map[lowBit(i)];
change_state(x, y, t);
board[x][y] = (char)('1' + t);
if(dfs(cnt - 1, board)) return true;
//恢复现场
change_state(x, y, t);
board[x][y] = '.';
}
return false;
}
void change_state(int x, int y, int t){
row[x] ^= 1 << t;
col[y] ^= 1 << t;
cell[x / 3][y / 3] ^= 1 << t;
}
int get(int x, int y){
return row[x] & col[y] & cell[x / 3][y / 3];
}
int lowBit(int x){
return -x & x;
}
}