用二进制位记录冲突信息，用位运算替代效率较低的哈希运算。

题目链接-来源：力扣（LeetCode）

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例：

输入：board = [[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”],[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”],[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”],[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”],[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”],[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”],[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”],[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”],[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
输出：[[“5”,”3”,”4”,”6”,”7”,”8”,”9”,”1”,”2”],[“6”,”7”,”2”,”1”,”9”,”5”,”3”,”4”,”8”],[“1”,”9”,”8”,”3”,”4”,”2”,”5”,”6”,”7”],[“8”,”5”,”9”,”7”,”6”,”1”,”4”,”2”,”3”],[“4”,”2”,”6”,”8”,”5”,”3”,”7”,”9”,”1”],[“7”,”1”,”3”,”9”,”2”,”4”,”8”,”5”,”6”],[“9”,”6”,”1”,”5”,”3”,”7”,”2”,”8”,”4”],[“2”,”8”,”7”,”4”,”1”,”9”,”6”,”3”,”5”],[“3”,”4”,”5”,”2”,”8”,”6”,”1”,”7”,”9”]]

思路：

解数独本质上还是图的遍历模板，可以考虑用 DFS + 回溯的模板来解决。从某一个空格出发，递归地向外拓展，当发生冲突之后就回溯到之前未冲突的状态。
回溯算法要求我们尽可能对解空间进行剪枝（也就是尽量排除某个格子不可能的选项）。我们可以借鉴上一题的做法，用 27 个哈希表记录行、列、九宫格的冲突信息。
例如，对于一个行 [5, 3, , , 7, , , , ] 而言，行哈希表会记录 ‘5’、’3’、’7’ 三个数字，当欲在行中第 2 列添加新的答案时，我们还要将该行哈希表 与第 2 列所在的列哈希表、该元素所在的九宫格哈希表取并集。新元素先与并集中判断是否有哈希冲突，没有则加入之，然后继续进行 DFS，待下层递归返回后再删除哈希表中的这个答案。
优化：
不用哈希表，改用二进制位存储冲突信息。因为每个行、列或九宫格中从 ‘1’ ~ ‘9’ 的元素会且仅会出现一次，我们可以用一个 9 位二进制数，第 n 位的数字为 1 表示该行/列/九宫格 中已有了数字 n 。例如对于上面的行 [5, 3, , , 7, , , , ]，第 5、3、7 位就应该为 1，于是该二进制数可以表示为 001010100。当加入新元素时，我们只需要将行/列/九宫格所在二进制数按位或运算取并集，即可将为 0 的位对应的元素作为选项尝试填入，填入后该位置 1，待下层 DFS() 返回后再复位。
进一步优化：
为了减少无效的遍历，我们希望填入的数字尽可能不要触发回溯。我们可以遍历整个棋盘，对于每个空格，如果可填入的数字只有 1 种可能，那么这种空格就一定不会触发回溯。当我们遍历一次棋盘，新填入的数字会压缩其他空格的可能性，可能会有新的空格可能性降为 1。我们不停地循环，直到某一轮遍历后没有空格被修改为止。之后再开始 DFS。
时间复杂度：O(9^(9 * 9))
空间复杂度：O(1)

实现：

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
class Solution {
    public void solveSudoku(char[][] board) {
        this.board = board;
        for (int i = 0; i < 81; i++) {
            avail.add(i);
        }
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int val = board[i][j];
                if (val != '.') {
                    count++;
                    avail.remove(i * 9 + j);
                    val -= '1';
                    row[i] |= 1 << val;
                    col[j] |= 1 << val;
                    sqr[(i / 3) * 3 + j / 3] |= 1 << val;
                } 
            }
        }
        
        //Only one choice - Circle until no one-choice slot
        while (true) {
            boolean dirty = false;
            for (int slot = 0; slot < 81; slot++) {
                int i = slot / 9, j = slot % 9, sqrI = (i / 3) * 3 + j / 3; 
                if (!avail.contains(slot)) { 
                    continue;
                } 
                int intersection = (~(row[i] | col[j] | sqr[sqrI])) & 0x1ff; 
                if ((intersection & (intersection - 1)) == 0) {
                    char toFill = (char) (Integer.bitCount(intersection - 1) + '1');
                    count++;
                    dirty = true; 
                    avail.remove(slot);
                    row[i] |= intersection; 
                    col[j] |= intersection; 
                    sqr[sqrI] |= intersection;
                    board[i][j] = toFill; 
                } 
            } 
            if (!dirty) {
                break; 
            }
        }
        
        //
        DFS();
    }
    private int count = 0;
    private char[][] board;
    private int[] row = new int[9], col = new int[9], sqr = new int[9];
    private Set<Integer> avail = new LinkedHashSet<>();
    
    private void DFS () {
        if (count == 81) {
            return;
        }
        
        Iterator<Integer> it = avail.iterator();
        if (it.hasNext()) {
            int slot = it.next();
            int i = slot / 9, j = slot % 9, sqrI = (i / 3) * 3 + j / 3;
            
            int intersection = ((~row[i]) & (~col[j]) & (~sqr[sqrI]) & 0x1ff);
                        
            while (intersection != 0) {
                int marked = intersection & (-intersection);
                intersection ^= marked;
                char choice = (char) (Integer.bitCount(marked - 1) + '1');
                
                count++;
                avail.remove(slot);
                row[i] |= marked;
                col[j] |= marked;
                sqr[sqrI] |= marked;
                board[i][j] = choice;
                DFS();
                if (count == 81) {
                    return;
                }
                count--;
                avail.add(slot);
                row[i] ^= marked;
                col[j] ^= marked;
                sqr[sqrI] ^= marked;
                board[i][j] = '.';
            }
        }
    }
}