题解 | #Sudoku#

#include <iostream>
#include <vector>

using namespace std;

int SIZE=9;

bool isValidNum(const vector<vector<int>> &board,const int &row,const int &col,const int &num){
    for(int i=0;i<SIZE;i++){
        if(board[row][i]==num || board[i][col]==num)
            return false;
    }

    int rowstart=row-row%3,colstart=col-col%3;

    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(board[rowstart+i][colstart+i]==num)
                return false;
        }
    }

    return true;
}

bool SolveSuduku(vector<vector<int>> &board,int row,int col){
    if(row==SIZE-1 && col==SIZE)
        return true;

    if(col==SIZE){
        row++;
        col=0;
    }

    if(board[row][col]!=0)
        return SolveSuduku(board, row, col+1);

    for(int num=1;num<=9;num++){
        if(isValidNum(board, row, col, num)){
            board[row][col]=num;
            if(SolveSuduku(board, row, col+1))
                return true;
            board[row][col]=0;
        }
    }

    return false;
    
}

int main() {
    vector<vector<int>> board(9,vector<int>(9,0));
    int num;
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            cin>>num;
            board[i][j]=num;
        }
    }
    SolveSuduku(board, 0, 0);
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            cout<<board[i][j]<<' ';
        }
        cout<<endl;
    }
}
// 64 位输出请用 printf("%lld")

判断一个数字是否能填入，之后逐个dfs+回溯