Counting garlic customers: Sudoku (DFS)

The sample input

* 2 6 * * * * * *
* * * 5 * 2 * * 4
* * * 1 * * * * 7
* 3 * * 2 * 1 8 *
* * * 3 * 9 * * *
* 5 4 * 1 * * 7 *
5 * * * * 1 * * *
6 * * 9 * 7 * * *
* * * * * * 7 5 *

Sample output

1 2 6 7 3 4 5 9 8
3 7 8 5 9 2 6 1 4
4 9 5 1 6 8 2 3 7
7 3 9 4 2 5 1 8 6
8 6 1 3 7 9 4 2 5
2 5 4 8 1 6 3 7 9
5 4 7 2 8 1 9 6 3
6 1 3 9 5 7 8 4 2
9 8 2 6 4 3 7 5 1

Answer key ： This topic is similar to the eight queens problem , It's just that the eight queens are for each line 1−8 Attempts to , And this topic is about each empty space 1−9 Attempts to . And the problem can be ended when a feasible solution is found .
The marking method is to mark whether a line or a number appears , Mark whether a number in a column appears , Mark whether a small square or a number appears .
Be careful ：0-8 The marking method of a palace is ： Line number /3*3+ Column number /3,scanf Of c% Put a space in front , Counteract the effect of input spaces

#include<bits/stdc++.h>
using namespace std;
char mp[20][20];
bool f;
bool r[20][20],c[20][20],gong[20][20];
void dfs(int x,int y){
    
    if(f){
    
        return;// A situation has been found , sign out 
    }
    if(x==9){
    // At the end of the line, find a legal situation to print 
        for(int i=0;i<9;i++){
    
        for(int j=0;j<9;j++){
    
            cout<<mp[i][j];
            if(j!=8) cout<<" ";
            else cout<<endl;
        }
    }
        f=true;
        return;
    }
    if(y==9){
    // If a column is placed , Place the next line 
        dfs(x+1,0);
        return;
    }
    if(mp[x][y]!='*'){
    // If there are already numbers , Continue to place the next column 
        dfs(x,y+1);
        return;
    }
    
    for(int j=1;j<=9;j++){
    // Enumerate and place... On a location 1-9 The situation of 
        if(!r[x][j]&&!c[y][j]&&!gong[x/3*3+y/3][j]){
    // If you can , Column , There is no such number in the palace , You can put 
            r[x][j]=true;
            c[y][j]=true;
            gong[x/3*3+y/3][j]=true;
            mp[x][y]='0'+j;
            dfs(x,y+1);// Continue to place the next column 
            r[x][j]=false;// to flash back 
            c[y][j]=false;
            gong[x/3*3+y/3][j]=false;
            mp[x][y]='*';
        }
    }
}
int main(){
    
    for(int i=0;i<9;i++){
    
        for(int j=0;j<9;j++){
    
            scanf(" %c",&mp[i][j]);// Be careful scanf Of c% Put a space in front , Counteract the effect of input spaces 
        }
    }
    for(int i=0;i<9;i++){
    
        for(int j=0;j<9;j++){
    
            if(mp[i][j]!='*'){
    // Preprocessing mark 
                r[i][mp[i][j]-'0']=true;
                c[j][mp[i][j]-'0']=true;
                gong[i/3*3+j/3][mp[i][j]-'0']=true;
            }
        }
    }
    dfs(0,0);
    return 0;
}