力扣算法回溯篇：解数独

本文主要是介绍力扣算法回溯篇：解数独，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题解：
1、确定回溯函数参数

bool backtracking(vector<vector<char>>& board)

2、确定递归终止条件
无终止条件 填满为止
3、单层搜索过程
双重循环遍历棋盘，然后递归遍历某位置放9个数字的可能性

class Solution {
public:
    bool isVaild(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;
    }
    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++){
                    if(isVaild(i,j,k,board)){
                        //有效
                        board[i][j] = k;
                        if(backtracking(board)){
                            return true;
                        }
                        board[i][j]='.';
                    }
                }
                //9个数都不行
                return false;
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

这篇关于力扣算法回溯篇：解数独的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！