题解 | 数独

解法一：递归回溯

递归参数：

• 因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值，

终止条件：

• 递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！

判断棋盘是否合法有如下三个维度：

• 同行是否重复
• 同列是否重复
• 9宫格里是否重复

图片；来自Carl大佬的[D码随想录]

C++参考代码：

class Solution {
private:
bool backtracking(vector<vector<char>>& board) {
    for (int i = 0; i < board.size(); i++) {        // 遍历行
        for (int j = 0; j < board[0].size(); j++) { // 遍历列
            if (board[i][j] != '.') continue;
            for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适
                if (isValid(i, j, k, board)) {
                    board[i][j] = k;                // 放置k
                    if (backtracking(board)) return true; // 如果找到合适一组立刻返回
                    board[i][j] = '.';              // 回溯，撤销k
                }
            }
            return false;                           // 9个数都试完了，都不行，那么就返回false
        }
    }
    return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
    for (int i = 0; i < 9; i++) { // 判断行里是否重复
        if (board[row][i] == val) {
            return false;
        }
    }
    for (int j = 0; j < 9; j++) { // 判断列里是否重复
        if (board[j][col] == val) {
            return false;
        }
    }
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == val ) {
                return false;
            }
        }
    }
    return true;
}
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

复杂度分析：

时间复杂度：
由于这些方法均以递归 + 回溯为基础，算法运行的时间（以及时间复杂度）很大程度取决于给定的输入数据，而我们很难找到一个非常精确的渐进紧界。因此这里只给出一个较为宽松的渐进复杂度上界 ，即最多有9×9 个空白格，每个格子可以填[1,9] 中的任意整数。

复杂度参考：LeetCode-Solution

空间复杂度：复杂度为 O(1) 在固定 9*9 的棋盘里，复杂度不随数据变化而变化。

解法二：位运算

经常玩数独的可能知道，在填数字的时候一般都是选择那些可填数字比少的位置来填，所以这里也可以使用这种方式。这里为了便于计算，稍微修改了一点，每行每列每个单元格都使用一个int数字来记录，因为int类型是32位，而数独的行和列以及单元格大小都是9，所以使用int来存储足够了，这里只使用int类型的低9位来存储。举个简单的例子，比如第一行已经填了3个数字，比如示例中的5，3，7。那么我们就可以使用一个int类型的数字来表示

该解法参考作者：sdwwld

Java参考代码：

public class Solution {
               //数独的长宽大小
        final int N = 9;
        //行
        private int[] rows = new int[N];
        //列
        private int[] cols = new int[N];
        //单元格
        private int[][] cells = new int[3][3];

        public void solveSudoku(char[][] board) {
            //统计未填的个数
            int count = 0;