leetcode 37. 解数独（Java版）

题目描述（题目难度，困难）

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

一个数独.png
解数独.png
Note:

• 给定的数独序列只包含数字 1-9 和字符 '.' 。
• 你可以假设给定的数独只有唯一解。
• 给定数独永远是 9x9 形式的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sudoku-solver
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目求解

根据行、列、宫中的已填数字，得到空格处的可填数字。选择可填数字最少的空格，在可填数字中选择数字试填空格，更新对应行、列、宫空格中的可填数字。然后递归试填，如果试填失败，即出现存在空白格无数可填的情况，回溯，恢复到试填前的状态，试填下一元素，继续递归，直到能够所有空格都有数可填。
实际上就是深度优先的递归，算法框架如下所示：

for(遍历若干种可选情况){
    按当前选择的情况，更新数据。
    if(递归){
        递归成功，回溯。
    }else{
        递归失败，恢复数据到更新前的状态。
    }
}

算法细节上，要得到空格中的可填数字，就要综合三个方面的信息：

1. 空格所在行的已填数字的集合
2. 空格所在列的已填数字的集合
3. 空格所在宫的已填数字的集合

得到这三个集合后，对三个集合求并集，再对并集求一次补集，即可得到空格中可填数字的集合。
为了提高存储和运算的效率，可以按位表示信息，充分利用位运算以及位运算的各种技巧，来降低空间和时间上的复杂度。

运用到的位运算技巧大致如下：

• 指定位 置 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;
    }
}