解数独

Leetcode 37

学习记录自代码随想录

编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

要点：1.树层为1-9遍历，深度为board中从一开始的空格到最后一个空格；
2.递归时不需要先找出所有空格在利用一个循环递归深度，应该用两个循环（横纵坐标）定位来进行深度递归；
3.相比较之前的组合，排列问题回溯模板，需要在树层for循环外套两个for循环来辅助进行深度递归；
4.递归函数返回值为bool，因为题目只有一个解，所以只要找到一个解就立即返回；
5.对一个空格进行1-9的树层遍历，若没有满足条件的数字，则直接返回false（所以不需要最开始的终止条件）；

class Solution {
private:
    // board中元素为字符，输入参数应为char而不是int，数字字符不要想当然为int
    bool check(vector<vector<char>>& board, int row, int col, char target){
        // 检查行
        for(int j = 0; j < 9; j++){
            if(board[row][j] != '.' && board[row][j] == target){
                return false;
            }
        }

        //检查列
        for(int i = 0; i < 9; i++){
            if(board[i][col] != '.' && board[i][col] == target){
                return false;
            }
        }

        //检查九宫格
        int m = row / 3, n = col / 3;
        //下面注释的这种写法同加同减是对绞线检查不是遍历九宫格，不要相当然大意
        // for(int i = 3*m, j = 3*n; i < 3*m+3 && j < 3*n+3; i++, j++){
        //     if(board[i][j] != '.' && board[i][j] == target){
        //         return false;
        //     }
        // }
        //应为
        for(int i = 3*m; i < 3*m + 3; i++){
            for(int j = 3*n; j < 3*n + 3; j++){
                if(board[i][j] != '.' && board[i][j] == target){
                    return false;
                }
            }
        }
        return true;
    }

    // 返回为逻辑真假
    bool backtracking(vector<vector<char>>& board){
        // 不需要终止条件，原因见下方

        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.'){
                    for(char k = '1'; k <= '9'; k++){
                        if(check(board, i, j, k)){
                            board[i][j] = k;
                            if(backtracking(board)) return true;
                            board[i][j] = '.';  // 回溯 
                        }
                    }
                    // 如果9个数都不行返回假
                    // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                    // 那么会直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！
                    return false;
                }
            }
        }
        return true;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {

        backtracking(board);
    }
};