题目

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

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

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

示例 1：
数独1.jpg

输入：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"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

数独2.jpg

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'

题目数据保证输入数独仅有一个解

解题方法

递归回溯

数独问题一共有81个位置(0-80)需要填充数据，使用矩阵保存这81个位置中的元素，并通过递归回溯求解每一个位置的可能解。
但是每次都需要在原矩阵中查询已经出现过的数字，耗时较长。

class Solution {
  public:
  bool check(int x, int y, char s, vector<vector<char>>& board) {
      for (int i = 0; i<9; i++) {
          if (board[x][i] == s || board[i][y] == s)     return false;
      }
      for (int i = 0; i < 3; i++) {
          for (int j = 0; j < 3; j++) {
              if (board[x/3*3+i][y/3*3+j] == s)     return false;
          }
      }
      return true;
  }
  bool fill(int pos, vector<vector<char>>& board) {
      if (pos==81) return true;
      int x = pos/9;
      int y = pos%9;
      if (board[x][y]!='.')   return fill(pos+1, board);
      for (int i = 1; i<10; i++) {
          char s = '0'+i;
          if (check(x, y, s, board)) {
              board[x][y]= s;
              if (fill(pos+1, board))   return true;
              board[x][y] = '.';
          }
      }
      return false;
  }
  void solveSudoku(vector<vector<char>>& board) {
      fill(0, board);
  }
};

递归回溯（数组优化）

在暴力递归回溯的基础上，通过数组表达每行、每列、每块已经出现过得数字，缩小递归范围，缩短查询时间。 ```cpp class Solution { private: bool line[9][9]; bool column[9][9]; bool block[3][3][9]; bool valid; vector> spaces;

public: void dfs(vector>& board, int pos) { if (pos == spaces.size()) { valid = true; return; }

    auto [i, j] = spaces[pos];
    for (int digit = 0; digit < 9 && !valid; ++digit) {
        if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
            line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
            board[i][j] = digit + '0' + 1;
            dfs(board, pos + 1);
            line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
        }
    }
}

void solveSudoku(vector<vector<char>>& board) {
    memset(line, false, sizeof(line));
    memset(column, false, sizeof(column));
    memset(block, false, sizeof(block));
    valid = false;

    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] == '.') {
                spaces.emplace_back(i, j);
            }
            else {
                int digit = board[i][j] - '0' - 1;
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
            }
        }
    }

    dfs(board, 0);
}

};

<a name="LP3xI"></a>
## 递归回溯（位运算优化）
由于可能的填写数组仅为`1-9`，因此可以考虑通过二进制中每一位表示对应数字是否出现，减少空间占用。其中涉及到的未操作包括：

- **确定当前位置的可用数字：**`line[x]` `colum[y]` 和`box[x/3][y/3]`分别表示了当前位置所在行、列、区块中已经存在的数字。因此对上述变量进行或运算`|`随后取反`~`便可表示当前位置可以填入的数字。除此之外，还需要与`0x1FF`进行与运算`&`去除高位的影响。
- **位运算表示某个数字：**通过将`1`左移`<<`指定位数`digit-1`表示`digit`这一数字。
- **枚举当前所有可用数字：**可用数字保存在`mask`中，通过`mask & (-mask)`可以将最低位的`1`保留。再通过内置函数`__builtin_ctz()`求出具体的位数。
- **去除已经枚举的数字：**通过`mask &= (mask-1)`去除已经枚举过的低位数字。
```cpp
class Solution {
private:
    int line[9];
    int colum[9];
    int box[3][3];
    vector<pair<int, int>> spaces;
    bool valid;

public:
    void flid(int x, int y, int digit) {
        line[x] ^= (1<<digit);
        colum[y] ^= (1<<digit);
        box[x/3][y/3] ^= (1<<digit);
    }

    void dfs(vector<vector<char>>& board, int pos) {
        if(pos==spaces.size()) {
            valid = true;
            return;
        }

        auto [x, y] = spaces[pos];
        int mask = ~(line[x] | colum[y] | box[x/3][y/3]) & 0x1FF;
        for (; mask && !valid; mask &= (mask-1)) {
            int digitmask = mask & (-mask);
            int digit = __builtin_ctz(digitmask);
            flid(x, y, digit);
            board[x][y] = digit + '0' +1;
            dfs(board, pos+1);
            flid(x, y, digit);
        }
    }

    void solveSudoku(vector<vector<char>>& board) {
        memset(line, 0, sizeof(line));
        memset(colum, 0, sizeof(colum));
        memset(box, 0, size(box));

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

        dfs(board, 0);
    }
};

枚举优化

在位运算的优化基础上对枚举进行优化，缩小枚举范围。具体为不断遍历数组，直接确定只有一种可填入数字的位置，并对其进行填入。

class Solution {
private:
    int line[9];
    int column[9];
    int block[3][3];
    bool valid;
    vector<pair<int, int>> spaces;

public:
    void flip(int i, int j, int digit) {
        line[i] ^= (1 << digit);
        column[j] ^= (1 << digit);
        block[i / 3][j / 3] ^= (1 << digit);
    }

    void dfs(vector<vector<char>>& board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }

        auto [i, j] = spaces[pos];
        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
        for (; mask && !valid; mask &= (mask - 1)) {
            int digitMask = mask & (-mask);
            int digit = __builtin_ctz(digitMask);
            flip(i, j, digit);
            board[i][j] = digit + '0' + 1;
            dfs(board, pos + 1);
            flip(i, j, digit);
        }
    }

    void solveSudoku(vector<vector<char>>& board) {
        memset(line, 0, sizeof(line));
        memset(column, 0, sizeof(column));
        memset(block, 0, sizeof(block));
        valid = false;

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

        bool modefied;
        while (1) {
            modefied = false;
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (board[i][j] == '.') {
                        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
                        if (! mask & (mask-1)) {
                            int digit = __builtin_ctz(mask);
                            flip(i, j, digit);
                            board[i][j] = digit +'0'+1;
                            modefied = true;
                        }
                    }
                }
            }
            if (!modefied) break;
        }

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.emplace_back(i, j);
                }
            }
        }

        dfs(board, 0);
    }
};

LeetCode

37. 解数独

题目

解题方法

递归回溯

递归回溯（数组优化）

枚举优化