题解 | #Sudoku#

#include <iostream>
using namespace std;
#include<vector>

//剪枝
bool isValid(vector<vector<int>>& board,int row,int col,int num){
    for(int i =0;i<9;i++){
        if(board[row][i]==num||board[i][col]==num){
            return false;
        }
        if(board[(row/3)*3+i/3][(col/3)*3+i%3]==num){
            return false;
        }
    }
    return true;
}

bool solveSudoku(vector<vector<int>>& board){
    for(int row = 0;row<9;row++){
        for(int col = 0;col<9;col++){//遍历数独矩阵

            if(board[row][col] == 0){//找到0，开始填空
                for(int num=1;num<=9;num++){
                    if(isValid(board, row, col, num)){
                        board[row][col] = num;
                        if(solveSudoku(board)){
                            return true;
                        }
                        board[row][col]=0;//当前的num无解，置零回溯选择下一个合适的num
                    }
                }

                return false;
            }
        }
    }
    return true;
}
int main() {
    vector<vector<int>> board(9,vector<int>(9));
    for(int i=0;i<9;i++){
        for(int j = 0;j<9;j++){
            cin>>board[i][j];
        }
    }

    if(solveSudoku(board)){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                cout<<board[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")