题目描述

传送门-力扣

编写一个程序，通过已填充的空格来解决数独问题。一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
Note:
给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

思路

开始觉得是个很难的题，看了答主：代码随想录 的回答后，觉得思路简单清洗，代码也很容易理解，遂记录一下。
采用“回溯+递归”的方法，其中
1. 回溯：从第一个空格（‘.’）开始，选择一个复合规则的数字填入，再处理下一个空格，当填到某一个空格后无法继续进行时，则回溯到上一个步骤，更改上一个空格填的数字后再继续处理下一个空格。
2. 递归：当填了第一个空格后，剩下的待填写空格处理方式和第一个空格相同，因此继续调用该函数处理。
细节处理：
1. 判断填入的数字是否符合规则。
2. 递归函数的出口处理

代码

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        backTracking(board);
    }

private:
    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 c = '1'; c <= '9'; c++){       //分别取数字1-9
                    if(isInplace(i, j, c, board)){      //判断填入改数字是否符合规则
                        board[i][j] = c;                //符合规则，则修改该空格
                        if(backTracking(board))         //递归，处理修改后的新的数独问题
                            return true;
                        board[i][j] = '.';              //当无法继续，则回溯，修改会空格
                    }
                }
                return false;
            }
        }
        return true;
    }

    //判断填入的数字是否符合规则
    bool isInplace(int row, int col, char c, vector<vector<char>>& board){
        for(int i = 0; i < 9; i++)
            if(board[row][i] == c)
                return false;

        for(int i = 0; i < 9; i++)
            if(board[i][col] == c)
                return false;

        int row3 = (row / 3) * 3;
        int col3 = (col / 3) * 3;
        for(int i = row3; i < row3 + 3; i++)
            for(int j = col3; j < col3 + 3; j++)
                if(board[i][j] == c)
                    return false;

        return true;
    }
};