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

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

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

一个数独。

答案被标成红色。

提示：

• 给定的数独序列只包含数字 1-9 和字符 '.' 。
• 你可以假设给定的数独只有唯一解。
• 给定数独永远是 9x9 形式的。

Solution

参考思路：**@luo-bi-da-quan**

• 回溯算法

# @lc code=start
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        nums = {"1", "2", "3", "4", "5", "6", "7", "8", "9"}
        row = [set() for _ in range(9)]
        col = [set() for _ in range(9)]
        palace = [[set() for _ in range(3)] for _ in range(3)]  # 3*3
        blank = []
        
        # 初始化，分别存入哈希表
        for i in range(9):
            for j in range(9):
                ch = board[i][j]
                if ch=='.':
                    blank.append((i, j))
                else:
                    row[i].add(ch)
                    col[j].add(ch)
                    palace[i//3][j//3].add(ch)
        
        def dfs(n):
            if n==len(blank):
                return True
            i, j = blank[n]
            restNum = nums - row[i]-col[j]-palace[i//3][j//3]
            if not restNum:
                return False
            for num in restNum:
                board[i][j] = num
                row[i].add(num)
                col[j].add(num)
                palace[i//3][j//3].add(num)
                if dfs(n+1):
                    return True
                row[i].remove(num)
                col[j].remove(num)
                palace[i//3][j//3].remove(num)
        
        dfs(0)
                
# @lc code=end

参考 @carlsun-2 的题解

• 需要一个二维的递归（也就是两个for循环嵌套着递归）

• 一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！

class Solution {
private:
    bool dfs(vector<vector<char>>& board){
        for(int i=0; i<9; ++i){
            for(int j=0; j<9; ++j){
                if(board[i][j] != '.')
                    continue;
                for(char c='1'; c<='9'; c++){
                    if(isValid(board, i, j, c)){
                        board[i][j]=c;
                        if(dfs(board))
                            return true;
                        board[i][j]='.';
                    }
                }
                return false; // 9 个试完都不合适，返回 false
            }
        }
        return true; // 遍历完没返回 false，说明找到
    }

    bool isValid(const vector<vector<char>>& board, int row, int col, char c){
        for(int i=0; i<9; ++i){
            // 判断行是否重复
            if(board[row][i]==c) return false;
            // 判断列是否重复
            if(board[i][col]==c) return false;
            // 判断 3x3 方框内是否重复
            if(board[(row/3)*3 + i/3][(col/3)*3 + i%3]==c) return false;
        }
        return true;
    }

public:
    void solveSudoku(vector<vector<char>>& board) {
        dfs(board);
    }
};