GFG PTOD | 31 Jan | Solve the Sudoku | Hard level | Backtracking

bool setisfy(vector<vector<int>> &mat, int i, int j, int num) {
        for(int x= 0; x<9; x++) {
            if(mat[i][x] == num || mat[x][j] == num) 
                return false;
        }
        int str = i-i%3, stc = j-j%3;
        for(int a=0; a<3; a++){
            for(int b=0;b<3; b++) {
                if(mat[str+a][stc+b] == num)
                    return false;
            }
        }
        return true;
    }
    
    bool solve(vector<vector<int>> &mat)  {
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                if(mat[i][j] == 0) {
                    for(int num = 1; num<=9; num++) {
                        if(setisfy(mat, i, j, num)) {
                            mat[i][j] = num;
                            if(solve(mat)) return true;
                            mat[i][j] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    // Function to find a solved Sudoku.
    void solveSudoku(vector<vector<int>> &mat) {
        // code here
        solve(mat);
    }