题解 | 数独

#include <bits/stdc++.h>
#include <vector>
using namespace std;

class Solution{
    private:
    bool isValid(vector<vector<int>>& board,int row,int col,int num){
        for(int i=0;i<9;i++) if(board[row][i]==num) return false;
        for(int i=0;i<9;i++) if(board[i][col]==num) return false;
        int startrow = row-row%3;
        int startcol = col-col%3;
        for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(board[startrow+i][startcol+j]==num) return false;
        return true;
    }
    bool solve(vector<vector<int>>& board){
        for(int i=0;i<9;i++) for(int j=0;j<9;j++){
            if(board[i][j]==0){
                for(int num=1;num<10;num++){
                    if(isValid(board,i,j,num)){
                        board[i][j]=num;
                        if(solve(board)) return true;//继续向下进行
                        board[i][j]=0;//走不通便擦除，迭代填入下一个num
                    }
                }
                return false;//如果全部num填入都不行，返回false,擦除并换值
            }
        }
        return true;
    }
    public:
    void solvesolution(vector<vector<int>>& board){
        solve(board);
    }
};

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];
        }
    }
    Solution solution;
    solution.solvesolution(board);
    for(int i=0;i<9;i++) for(int j=0;j<9;j++) {
        cout<<board[i][j]<<" ";
        if(j==8) cout<<endl;
    }
}