1
2
3

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 回溯法
    pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
        let mut row: Vec<Vec<bool>> = vec![vec![false; 9]; 9];
        let mut col: Vec<Vec<bool>> = vec![vec![false; 9]; 9];
        let mut mini: Vec<Vec<bool>> = vec![vec![false; 9]; 9];
        for i in 0..board.len() {
            for j in 0..board.len() {
                if board[i][j] == '.' {
                    continue;
                }
                let num = ((board[i][j] as u32) - ('1' as u32)) as usize;
                row[i][num] = true;
                col[j][num] = true;
                let k = ((i / 3) + j % 3) as usize;
                mini[k][num] = true;
            }
        }

        return Self::fill(board, 0, &mut row, &mut col, &mut mini);
    }

    fn fill(
        board: &mut Vec<Vec<char>>,
        n: u32,
        row: &mut Vec<Vec<bool>>,
        col: &mut Vec<Vec<bool>>,
        mini: &mut Vec<Vec<bool>>,
    ) {
        let n = n as usize;
        if n >= 9 {
            return;
        }
        for i in 0..board.len() {
            for j in 0..board.len() {
                if board[i][j] == '.' {
                    //
                    let k = ((i / 3) + j % 3) as usize;
                    if n <= 9 && !row[i][n] && !col[j][n] && !mini[k][n] {
                        board[i][j] = char::from_u32(n as u32).unwrap();
                        Self::fill(board, (n + 1) as u32, row, col, mini);
                        board[i][j] = '.';
                    }
                }
            }
        }
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

class Solution {
    bool col[9][9];         //第i行字符c是否已经存在；
    bool row[9][9];         //第j列字符c是否已经存在;
    bool cell[9][9];        //小单元中的字符监测

public:
    /*
    * ## 解题思路
    * * 回溯法
    *   1. 对于每个空位，依次使用1-9字符进行尝试 f(idx)
    *   2. 如果冲突，则尝试用下一个字符尝试；
    *   3. 如果不冲突，继续尝试后续 f(idx+1)
    *      3.1 如果后续尝试合法(当前也合法)，则得到一个解；
    *      3.2 如果不合法，则需要回退当前
    *   4. 如果字符1-9都尝试完，还没有合法的，则false；
    */
    void solveSudoku(vector<vector<char>>& board) {
        // 初始化
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                char c=board[i][j];
                int k=3*(i/3)+j/3;
                if (c!='.') {
                    int ci=c-'1';
                    col[i][ci]=row[j][ci]=cell[k][ci] = true;
                }
            }
        }

        tryFillCharAtIdx(board, 0);
    }

    bool isCharValid(int i, int j, char c) {
        int k=3*(i/3)+j/3;
        int ci=c-'1';
        return (!col[i][ci] && !row[j][ci] && !cell[k][ci]);
    }

    /**
    * 往第idx个格子出填充字符
    */
    bool tryFillCharAtIdx(vector<vector<char>>& board, int idx) {
        // 所有格子已经填充完，则填充结束
        if (idx >= 81 ) {
            return true;
        }

        int i = idx / 9;    //所在行
        int j = idx % 9;    //所在列
        int k = 3*(i/3)+j/3; //所在cell

        //当前格子已填充字符
        if (board[i][j] != '.') {
            return tryFillCharAtIdx(board, idx+1);
        }

        //当前格子未填充
        // 尝试填充
        for(char c='1'; c<='9'; c++) {
            int ci=c-'1';

            //行,列或者单元格中已经存在c, 则换下一个字符
            if (!isCharValid(i, j, c)) {
                continue;
            }

            //填充当前格子
            board[i][j] = c;
            col[i][ci]=row[j][ci]=cell[k][ci] = true; //更新已填充的格子

            //继续填后面的空格
            if (tryFillCharAtIdx(board, idx+1)) {
                return true; //如果后面的也合法，为一个有效解, 可以返回；
            }

            //否则，后续无法填到合法的，撤回当前所填的数字
            col[i][ci]=row[j][ci]=cell[k][ci] = false; //恢复
            board[i][j] = '.';

            //重新尝试下一个数字
        }

        // 尝试完了所有字符，没有合法解，则
        return false;
    }
};