题目描述

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ’.’ 表示。

算法1

(DFS) $O((9!)^9)$

暴力搜索；
注意，搜到解了，就返回true打断，不要继续搜索了，否则又回溯到原来没填过的数独了。

时间复杂度

理论上每一行$9!$种填法，填9行，所以上界是$O((9!)^9)$，这里只考虑了行的约束，实际搜索空间肯定比这个更小。

参考文献

C++ 代码

class Solution {
private:
    bool row[9][10], col[9][10], block[9][10];
public:
    void solveSudoku(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        for (int r = 0; r < 9; ++r){
            for (int c = 0; c < 9; ++c){
                if (board[r][c] != '.'){
                    int num = board[r][c] - '0', b = r / 3 * 3 + c / 3;
                    row[r][num] = col[c][num] = block[b][num] = true;
                }
            }
        }

        dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char>> &board, int r, int c){
        if (r >= 9) return true;
        if (c >= 9){
            return dfs(board, r + 1, 0);
        }

        if (board[r][c] != '.'){
            return dfs(board, r, c + 1);
        }

        int b = r / 3 * 3 + c / 3;
        for (int i = 1; i <= 9; ++i){
            if (!row[r][i] && !col[c][i] && !block[b][i]){
                board[r][c] = '0' + i;
                row[r][i] = col[c][i] = block[b][i] = true;
                if (dfs(board, r, c + 1)) return true;
                row[r][i] = col[c][i] = block[b][i] = false;
                board[r][c] = '.';
            }
        }
        return false;
    }
};