编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
image.png
输入：

  1. board = [
  2. ["5","3",".",".","7",".",".",".","."],
  3. ["6",".",".","1","9","5",".",".","."],
  4. [".","9","8",".",".",".",".","6","."],
  5. ["8",".",".",".","6",".",".",".","3"],
  6. ["4",".",".","8",".","3",".",".","1"],
  7. ["7",".",".",".","2",".",".",".","6"],
  8. [".","6",".",".",".",".","2","8","."],
  9. [".",".",".","4","1","9",".",".","5"],
  10. [".",".",".",".","8",".",".","7","9"]
  11. ]

由于每个数字在同一行、同一列、同一个九宫格中只会出现一次，因此我们可以使用三个状态数组来表达这三种约束。
考虑到状态仅有两种可能，使用位运算来实现以减少空间消耗。具体地，数 b的二进制表示的第 i位（从低到高，最低位为第 0 位）为 1，当且仅当数字 i+1 已经出现过。例如当 b 的二进制表示为 (011000100)2时，就表示数字 3，7，8 已经出现过。

状态压缩

+回溯

  1. 使用数组line[9],column[9],block[3][3]来压缩存储每一行、每一列、每一个 3x3 宫格中 1-9 是否出现 。具体来说，line[0]表示第一行的1-9是否出现，如line[0]=111111111 表示第一行每个数字都出现了。
    2. 这样每一个格子就可以计算出所有不能填的数字，然后得到所有能填的数字 getPossibleStatus()
    3. 填入数字和回溯时，只需要更新存储信息
    4. 每个格子在使用时，会根据存储信息重新计算能填的数字
    ```java class Solution { \(也可以声明为局部变量以节省一丢丢的空间，但是方法参数会多四个) private int[] line = new int[9]; private int[] column = new int[9]; private int[][] block = new int[3][3]; private boolean valid = false; private List spaces = new ArrayList();

    public void solveSudoku(char[][] board) {

     for (int i = 0; i < 9; ++i) {
     for (int j = 0; j < 9; ++j) {
         if (board[i][j] == '.') {
             spaces.add(new int[]{i, j});
         } else {
             int digit = board[i][j] - '0' - 1;
             flip(i, j, digit);
         }
     }
 }

 dfs(board, 0);

    }

    public void dfs(char[][] board, int pos) {

     if (pos == spaces.size()) {
     valid = true;
     return;
 }

 int[] space = spaces.get(pos);
 int i = space[0], j = space[1];
 \\（之所以要 & 0x1ff是因为取非后，除了最后9位前面的一堆都是1）
 int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
 for (int k=0;k<9 && !valid;k++) {
     if((mask&1<<k)==0) continue;
     flip(i, j, k);
     board[i][j] = (char) (k + '0' + 1);
     dfs(board, pos + 1);
     flip(i, j, k);
 }

    }

    public void flip(int i, int j, int digit) {

     line[i] ^= (1 << digit);
 column[j] ^= (1 << digit);
 block[i / 3][j / 3] ^= (1 << digit);

    } }

``` image.png