LeetCode 37 解数独

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 ‘.’
题目数据保证输入数独仅有一个解

回溯递归

本质上就是给定一个 $9\times9$ 的二维矩阵，使用1-9对该二维矩阵进行补全。在补全矩阵后需要保证，在矩阵的每一行每一列中都不存在重复元素。并且在9个 $3\times3$ 的小方框中不存在重复的元素。并且这样的求解有且仅有一个。

采取逐行放置的方式：设计一个递归地回溯函数 bool backtrack(int row,int col,vector<vector<char>>& board) ，向函数传递的参数值为 row 行号和 col 列号，每一次仅填写 board[row][col] 位置处的元素，返回值为bool类型，表示本地递归是否找到了可行的解。首先判断 board[row][col] 位置处的元素是否是 . 若不是，则直接 col+1 向下递归，并且直接返回递归函数的返回值。

若是则使用一个hash used[9] 记录，在 board[row][col] 处那些元素是使用过的。首先是按行列进行统计，再按 $3\times3$ 的宫格进行统计。

bool used[9]={false};
for(int i=0;i<board[row].size();i++){ // 处理行
    if(board[row][i]!='.') used[board[row][i]-'1']=true;
}
for(int i=0;i<board.size();i++){ // 处理列
    if(board[i][col]!='.') used[board[i][col]-'1']=true;
}
// 处理粗线宫格
for(int i=row/3*3;i<row/3*3+3;i++){
    for(int j=col/3*3;j<col/3*3+3;j++){
        if(board[i][j]!='.')
            used[board[i][j]-'1']=true;
    }
}

完成统计后则开始尝试向 board[row][col] 处填入元素，填入元素后 col+1 向下递归。

当 col==board.size() 时说明当前 row 行已经填完，那么 backtrack(row+1,0, board) 向下递归。并且将递归函数的结果直接返回，递归结束的条件： row==board.size() 时，说明已经完成了矩阵中全部元素的处理。

总体代码：

class Solution {
public:
    bool backtrack(int row,int col,vector<vector<char>>& board){
        if(row==board.size()){
            return true;
        }
        if(col==board.size()){ // row行完成填写
            if(backtrack(row+1,0,board)){
                return true;
            }
            return false;
        }
        if(board[row][col]!='.'){// 已填数字
            if(backtrack(row,col+1,board))
                return true;
            return false;
        }
        bool used[9]={false};
        for(int i=0;i<board[row].size();i++){ // 处理行
            if(board[row][i]!='.') used[board[row][i]-'1']=true;
        }
        for(int i=0;i<board.size();i++){ // 处理列
            if(board[i][col]!='.') used[board[i][col]-'1']=true;
        }
        // 处理粗线宫格
        for(int i=row/3*3;i<row/3*3+3;i++){
            for(int j=col/3*3;j<col/3*3+3;j++){
                if(board[i][j]!='.')
                    used[board[i][j]-'1']=true;
            }
        }
        for(int i=0;i<9;i++){
            if(!used[i]){
                board[row][col]='1'+i;
                if(backtrack(row,col+1,board)){
                    return true;
                }
                board[row][col]='.';
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtrack(0,0,board);
    }
};

另一种处理思路：在递归函数中使用双层的for循环，按照行进行处理，每次逐行去寻找第一个未被填入的元素，向其中填入相应的元素，并判断填入的元素是否合法。

Mark's blogs

LeetCode-37-解数独

LeetCode 37 解数独

回溯递归