37. 解数独（难度：困难）

题目链接：https://leetcode-cn.com/problems/sudoku-solver/

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

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

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

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

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

解法一：回溯法

该算法思想比较简单，给每个方块都设置约束，在数独上面放入一个数字，则这行、这列、这块（3*3）的元素都不能对这个数字再进行使用。从而减少回溯遍历的次数。

我们只需要，逐行逐列的对每一个需要填写的数独赋以值，若当前正确，那么就进行下个数独的赋值；若出现了冲突，则开始回溯，尝试另一个可以的赋值。如果还是不行，那就再次回退。

如何查看是否冲突？

• 对该行进行遍历，查看是否有与新值相同的，即判断
  board[row][i] == ch
• 对该列进行遍历，查看是否有与新值相同的，即判断
  board[i][col] == ch
• 对该块进行遍历，查看是否有与新值相同的，即判断
  board[lumpRow][lumpCol] == ch
  • 其中lumpRow是指当前数独位置对应的块序号，
    lumpRow = (row / 3) * 3 + j / 3
  • 其中lumpCol是指当前数独位置在对应的块中的下标，即从左到右，从上到下依次排列的序号，
    lumpRow = (row / 3) * 3 + j / 3

算法思想：

（1）从左上角开始 row = 0,col = 0。直到到达第一个空方格。

（2）从 1 到 9 之间的数字d 依次尝试放入[row,col] 格子

（3）若 d 没有出现在当前行，列，方块中，则放入该方格中，进行下一个方格的尝试。

（4）若d出现在当前行或列或方块中，则回到到第（2）步，尝试下一个d。

（5）若所有的d都尝试完，仍然没有满足的，则回溯到上一步，即上一个方格的赋值进行更改，然后重复（2）以后的操作。

代码：

class Solution {
    public void solveSudoku(char[][] board) {
        sudaoKu(board, 0, 0);
    }

    private boolean sudaoKu(char[][] board, int row, int col) {
        int n = board.length; // 9

        // 若一行满了，跳转到下一行
        if (col == n) {
            return sudaoKu(board, row + 1, 0);
        }

        /*
         * 当到最后一个数独board[8][8]，
         * 若验证成功， 下来是board[8][9],满足上面条件，
         * 会到board[9][0], 
         * 当到这块说明数独找到解法了,
         * 此处是整个回溯算法的出口
         */
        if (row == n) {
            return true;
        }

        // 当该位置已经有数字，直接去找下一个未填数的位置
        if (board[row][col] != '.') {
            return sudaoKu(board, row, col + 1);
        }

        // 遍历填数
        for (char i = '1'; i <= '9'; i++) {
            // 验证放入i是否满足条件
            if (!verify(board, row, col, i)) {
                continue;
            }else {
                //将i放入该位置
                board[row][col] = i;
                //接着递归判断下一列元素
                //若成功找到解法，则返回true
                if(sudaoKu(board,row,col+1)) {
                    return true;
                }else {
                    //否则，回溯
                    board[row][col] = '.';
                }
            }
        }
        return false;
    }

    /*
     * 验证在[row,col]位置插入i，是否满足条件 只需验证同一行、同一列、同一方块是否存在重复
     * 
     */
    private boolean verify(char[][] board, int row, int col, char i) {

        for (int j = 0; j < 9; j++) {       
            // 根据j来遍历所在块，计算出该块中每个数独的位置，在整个board中的位置坐标。
            int lumpRow = (row / 3) * 3 + j / 3;
            int lumpCol = (col / 3) * 3 + j % 3;
            //判断所在行是否存在重复
            if(board[row][j] == i) return false;
            //判断所在列是否存在重复
            if(board[j][col] == i) return false;
            //判断所在块是否存在重复
            if(board[lumpRow][lumpCol] == i) return false;
        }
        return true;
    }
}

解法二：回溯法+状态压缩

思路：

1、状态压缩

（1）我们可以对每一行、每一列、每个3*3方块使用一个int数字来压缩存储他们中出现的数字。

（2）然后我们可以得到每一个方格都有对应的行、列、方块中已经出现的数字，从而可以得到没有出现的数字，也就是可以供选择填入的数字，这样我们就可以大大提高效率。

（3）我们可以选择约束最多的方格开始尝试赋值，这样可以大大减少我们回溯的次数，约束最多也就是指的在该方格的行和列以及3*3方块中出现不同数字的次数最多。

（4）在每次填入数字之后，对压缩存储信息的数组进行更新。

（5）根据压缩存储信息的更新，然后重新计算可以填入的数字。

那么我们如何使用一个int数字来压缩表示他们中出现的数字？

我们可以把每一个int 数字都想象成他的二进制形式。因为java中一个int类型的数字是32位，而我们若用每位来表示0-9之间的数字是否存在，只需要使用低位的9位。所以下面我只罗列地位的九位。

若我们使用171来表示一个压缩存储信息：

（1）在我们存储信息的时候，只需要对每一行、每一列、每个3*3方块 的int数字 进行或运算，即 rows[x] = rows[x] | 1<<n

（2）我们想要知道某个方格对应的行、列、方块已经存在的数字，只需要对他们进行或运算，即rows[x] | cols[y] | cells[x/3][y/3];

（3）若想拿到该方格可以填入的数字，只需要对上面表达式取反，即~(rows[x] | cols[y] | cells[x/3][y/3]);

（4）若想知道那个方格的约束最多，只需要对上述计算的已经存在的数字，计算出其二进制的1的个数，个数最多的表示约束最多。
我们可以利用Integer.bitCount() 方法刚好可以得到1的个数。

下图，不是自己做的，直接使用大佬的图：

代码：

class Solution {
        //解法二
    /* rows,cols,cells分别表示在某行、某列、某块已经出现的数字
     * 使用二进制表示
     * 如：    100010010
     * 对应：  987654321
     * 已经存在的数字：9,5,2
     */
    
    int rows[] = new int[9];
    int cols[] = new int[9];
    int cells[][] = new int[3][3];
    
    /*计算出[x,y]坐标可以填的数，用二进制表示可以填写的数
     * 如      100100010
     * 对应  987654321
     * 可以填写是数字为9,6,2
     */
    private int getPossibleStatus(int x,int y) {
        return ~(rows[x] | cols[y] | cells[x/3][y/3]);
    }
    
    /*
     * 找到能够填写数字的个数最小的那个位置，
     * 即通过getPossibleStatus方法得到的数字，转为二进制
     * 其中1的个数最小的那个位置
     */
    private Map<Integer, Integer> getNext(char[][] board) {
        Map<Integer, Integer> map = new HashMap<>();
        int min = 33;
        int r = 0,c =0;
        for(int i = 0;i<9;i++) {
            for(int j = 0;j<9;j++) {
                if(board[i][j] != '.') continue;
                int temp = getPossibleStatus(i, j);
                //计算其中包含1的个数，即可以填写的数字的个数
                int tempNum = Integer.bitCount(temp);
                if(tempNum >= min) continue;
                r = i;
                c = j;
                min = tempNum;
            }
        }
        map.put(r, c);
        return map;
    }
    
    /**
     * 更新三个数组的数据
     * flag若为true，则是更新指定位置的数为1，
     * 若为false则是，回调，将指定位置的数改为0.
     * @param x
     * @param y
     * @param n
     */
    private void fillNum(int x,int y,int n,boolean flag) {
        rows[x] = (flag)?(rows[x] | 1<<n):(rows[x] & (~(1<<n)) );
        cols[y] = (flag)?(cols[y] | 1<<n):(cols[y] & (~(1<<n)) );
        cells[x/3][y/3] = (flag)?(cells[x/3][y/3] | 1<<n):(cells[x/3][y/3] & (~(1<<n)) );
    }
    
    /**
     * 回溯方法
     * @param board
     * @param cnt
     * @return
     */
    boolean dfs(char[][] board,int cnt) {
        if(cnt == 0) {
            return true;
        }
        
        //计算出可填的数字个数最小的坐标
        Map<Integer, Integer> map = getNext(board);
        
        int x = 0,y = 0;
        //拿到x,y坐标
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            x = entry.getKey();
            y = entry.getValue();
        }
        
        //拿到可以填写的数字
        int bits = getPossibleStatus(x, y);
        
        //在指定位置填数
        for(int n = 0;n<9;n++) {
            //找到可以填的数字（挨个试）
            //若不是可以填写的数字则跳过
            if((bits & (1<<n)) == 0) continue;
            fillNum(x, y, n, true);
            board[x][y] = (char) (n + '1');
            if(dfs(board, cnt - 1)) 
                return true;
            //如若不能找到最终结果，则回调
            board[x][y] = '.';
            fillNum(x, y, n, false);
        } 
        return false;
    }
    
    
    public void solveSudoku(char[][] board) {
        //计算'.'的个数，即需要补空的个数
        int cnt = 0;
        
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                cnt += (board[i][j] == '.'? 1:0);
                if(board[i][j] == '.')
                    continue;
                int n = board[i][j] -'1';
                fillNum(i,j,n,true);
            }
        }
        dfs(board, cnt);
    }   
}