leetcode 37. 解数独（Java版）
2019-06-12 本文已影响0人
M_lear
题目描述（题目难度，困难）
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
空白格用 '.' 表示。
一个数独.png
解数独.png
Note:
- 给定的数独序列只包含数字
1-9和字符'.'。 - 你可以假设给定的数独只有唯一解。
- 给定数独永远是
9x9形式的。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sudoku-solver
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目求解
根据行、列、宫中的已填数字，得到空格处的可填数字。选择可填数字最少的空格，在可填数字中选择数字试填空格，更新对应行、列、宫空格中的可填数字。然后递归试填，如果试填失败，即出现存在空白格无数可填的情况，回溯，恢复到试填前的状态，试填下一元素，继续递归，直到能够所有空格都有数可填。
实际上就是深度优先的递归，算法框架如下所示：
for(遍历若干种可选情况){
按当前选择的情况，更新数据。
if(递归){
递归成功，回溯。
}else{
递归失败，恢复数据到更新前的状态。
}
}
算法细节上，要得到空格中的可填数字，就要综合三个方面的信息：
- 空格所在行的已填数字的集合
- 空格所在列的已填数字的集合
- 空格所在宫的已填数字的集合
得到这三个集合后，对三个集合求并集，再对并集求一次补集，即可得到空格中可填数字的集合。
为了提高存储和运算的效率，可以按位表示信息，充分利用位运算以及位运算的各种技巧，来降低空间和时间上的复杂度。
运用到的位运算技巧大致如下：
- 指定位 置 1：
t |= 1 << x - 指定位 置 0：
t &= ~(1 << x) - 指定位 取反：
t ^= 1 << x - 取指定位的值：
t & 1 << x - 将二进制数中的最后一个 1 置0（可以用来判断一个数是否为 2 的幂，也可以用来求二进制数中 1 的个数）：
t &= t-1
举例：
| 运算 | 结果 |
|---|---|
| t | 10100 |
| t-1 | 10011 |
| t & t-1 | 10000 |
- 保留二进制数中最后一个 1，其余 1 置0：
t &= -t
举例：
| 运算 | 结果 |
|---|---|
| t | 10100 |
| -t | 01100 |
| t & -t | 00100 |
参考代码：
class Solution {
static final short V_511 = 0b111111111;
public void solveSudoku(char[][] board) {
short[] bitHash = new short[27];
// 得到数独的位图，对应数独的每一行每一列每一个九宫格的填数状态
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j){
if(board[i][j] != '.'){
int t = 1 << board[i][j] - 49;
bitHash[i] |= t;
bitHash[9+j] |= t;
bitHash[18+i/3*3+j/3] |= t;
}
}
}
short[][] subArray = new short[9][9];
// subArray 数组包含数独空白格可填数字和可填数字个数的信息。
int blankCount = 0;
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j){
if(board[i][j] == '.'){
++blankCount; // 统计空格数
subArray[i][j] = (short)(bitHash[i] | bitHash[9+j] | bitHash[18+i/3*3+j/3]);
int t = subArray[i][j] ^ V_511, count = 0;
while(t > 0){ // 统计 t 中 1 的个数
t &= t-1;
++count;
}
subArray[i][j] |= count << 9;
}
}
}
solve(subArray, board, blankCount);
}
boolean solve(short[][] subArray, char[][] board, int blankCount){
if(blankCount == 0) return true;
int r = 0, c = 0, count = Integer.MAX_VALUE;
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j){
if((subArray[i][j]&V_511) == V_511) return false;
if(subArray[i][j] != 0 && (subArray[i][j] & ~V_511) < count){
r = i;
c = j;
count = subArray[i][j] & ~V_511;
}
}
}
short[] save = new short[21];
int t = subArray[r][c]^V_511;
for(int i = 0; i < (count>>9); ++i){
int v = t & -t; // 保留 t 二进制数中最后一个 1
t &= ~v;
int k = 0;
for(int m = 0; m < 9; ++m){
save[k++] = subArray[m][c];
if(m != c) save[k++] = subArray[r][m];
if(subArray[m][c] != 0 && (subArray[m][c]&v) == 0){
subArray[m][c] |= v;
subArray[m][c] -= 1<<9; // 更新计数
}
if(subArray[r][m] != 0 && (subArray[r][m]&v) == 0){
subArray[r][m] |= v;
subArray[r][m] -= 1<<9;
}
}
subArray[r][c] = 0;
for(int m = 0; m < 3; ++m){
for(int n = 0; n < 3; ++n){
int a = r/3*3+m, b = c/3*3+n;
if(a != r && b != c){
save[k++] = subArray[a][b];
if(subArray[a][b] != 0 && (subArray[a][b]&v) == 0){
subArray[a][b] |= v;
subArray[a][b] -= 1<<9;
}
}
}
}
if(solve(subArray, board, blankCount-1)){ // 递归回溯
char num = '0';
while(v > 0){
v >>= 1;
++num;
}
board[r][c] = num; // 填入对应数字
return true;
}else{ // 恢复 subArray 数组
k = 0;
for(int m = 0; m < 9; ++m){
subArray[m][c] = save[k++];
if(m != c) subArray[r][m] = save[k++];
}
for(int m = 0; m < 3; ++m){
for(int n = 0; n < 3; ++n){
int a = r/3*3+m, b = c/3*3+n;
if(a != r && b != c){
subArray[a][b] = save[k++];
}
}
}
}
}
return false;
}
}
