题解 | #Sudoku#

#include<iostream>
#include<algorithm>
using namespace std;
const int N=9;
int mp[N][N];
bool findAll=false;

bool check(int row,int col,int num)
{
    for(int i=0;i<N;i++)
    {
        if(mp[row][i]==num) return false;
    }
    for(int i=0;i<N;i++)
    {
        if(mp[i][col]==num) return false;
    }
    int row_start=row/3*3;
    int col_start=col/3*3;
    for(int i=row_start;i<row_start+3;i++)
    {
        for(int j=col_start;j<col_start+1;j++)
        {
            if(mp[i][j]==num) return false;
        }
    }
    return true;
}

void dfs(int row,int col)
{
    if(col==9)
    {
        row++;
        col=0;
    }
    if(row==9)
    {
        findAll=true;
        return ;
    }
    if(mp[row][col]==0)
    {
        for(int i=1;i<=N;i++)
        {
            if(check(row,col,i))
            {
                mp[row][col]=i;
                dfs(row,col+1);
                if(findAll) return;
                mp[row][col]=0;  
            }
        }
        
    }else dfs(row,col+1);
}

int main(int argc,char* argv[])
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            cin>>mp[i][j];
        }
    }
    dfs(0,0);
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            cout<< mp[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}