Leetcode 37. 解数独

Leetcode 37. 解数独

题目

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

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

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

思路

• 递归函数以及参数
  递归函数的返回值需要是bool类型，解数独找到一个符合的条件就立刻返回，相当于找到从根节点到叶子节点一条路径，所以需要bool返回值
• 递归终止条件：本题不需要递归终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回
• 两个for循环嵌套一个递归，一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放置9个数字的可能性。

代码

class Solution {
public:
    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] = '.';// 回溯 撤销放置
                    }
                }

                return false;// 所有的数字都尝试完毕  不合法 直接返回false
            }
        }
        return true;
    }

    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 i = 0; i < 9; i++)
        {
            // 判断同列是否重复
            if(board[i][col] == val)
            {
                return false;
            }
        }

        // 判断九宫格内是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        // 计算从当前位置开始的九宫格
        for(int i  = startRow; i < startRow + 3; i++)
        {
            for(int j = startCol; j < startCol + 3; j++)
            {
                // 循环遍历九宫格 看是否有数字重复
                if(board[i][j] == val)
                {
                    return false;
                }
            }
        }
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};


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