Sudoku (easy to understand)

The easy to understand method is dfs Simple explosive search , This article introduces the simplest and most brutal method , Direct violence search , There is no optimization .

Sudoku is also called 9 GongGe ( As shown in the figure below )
The numbers in each line cannot be repeated
The numbers in each column cannot be repeated
Every little girl 9 GongGe ( Matrix ) The numbers cannot be repeated
It can be seen that the above three are respectively a containing 1-9 Set

So we can set up three two-dimensional arrays to record each row 、 Each column 、 Every square array 1-9 The number of , So as to determine which numbers can be filled in each point . One dimension represents the row number 、 The first few columns 、 How many square arrays , Then two dimensions are used to record which numbers already exist ,1 Indicates presence ,0 Does not exist .
Suppose we enter the following data ：

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

that , Let's set up a two-dimensional array a[10][10] To store graphs , Then judge each input point , If the value corresponding to the currently entered point is not 0, Then record this point .row[10][10] Record line 、col[10][10] Record column 、g[10][10] Recording matrix . Enter the points in the second row and the third column ( The value is 3) For example ( We subscript the array from 1 Start , For convenience )
a[2][3]>0, Then mark the points

row[2][a[i][j]]=1、col[3]a[i][j]]=1、g[((i-1)/3)*3+(j-1)/3+1)][a[i][j]]=1.

The three marks above are the essence of Sudoku , Understand this , Sudoku is easy to understand .
The most difficult part here is the boundary problem of the square matrix , If you are not careful, you may make a mistake . Because we are going to 1-9 Divide into 3 Parts of , however 1~9 Divide 3 The boundary is not easy to handle 3/3 be equal to 1, But we want him in the first place , That is, it should be equal to 0,6/2 You should make him equal to 1, Should be and 4/3、5/3 All equal to 1, Because they are in the same square , Then we have to 1-9 Mapping to 0-8 Then divide it
(0~2)/3 The corresponding is 0
(3~5)/3 The corresponding is 1
(6~8)/3 The corresponding is 2
This perfectly avoids this problem , The subscript we set is from 1 At the beginning , But the result is from 0 Start , So we add to the result 1, From 0-8 Turned into 1-9. That is to say 9 The number of the square matrix .
Here we can process what data can be selected for each point , then dfs Traverse to find the right situation .

Then there is another question, which point to start from , Then how to find ！！！
The title says violence search , Then I will start from the position (1,1) Begin your search , Column by column search , Search one line , So start with the first data in the next line . The title is sure to be solved in Sudoku , So when we find the location (9,9) when , Then we have reached the end , It means that the Sudoku filling has been completed , therefore , Just print the filled figure directly .( Students who understand can write their own code first , Children's shoes that do not understand can be understood with the help of the following code )

Code in AcWing And falling valley have passed the test
AcWing Title link on ： Simple Sudoku

#include<iostream>
#include<cstdio>
using namespace std;
const int N=10;
//a Used for drawing and saving 、col[i] Record No. i Number of columns that already exist 
//row[i] Record No. i The number of rows that already exist 、g[i] Record No. i The number of blocks that already exist 
int a[N][N],col[N][N],row[N][N],g[N][N];
//inline  It's an inline function , Non recursive functions work only when used 
// The function is that the program does not treat it as a function , It saves the time for the program to call the function 
// Use inline To save time , fast ！！！
inline void pr()
{
    
    for(int i=1;i<N;i++)
    {
    
        for(int j=1;j<N;j++)
            printf("%d",a[i][j]);
        puts("");// This is equivalent to a blank space 
    }
    exit(0);// Here is a little optimization , Find it and end the program directly , There's no need to keep looking 
}
void dfs(int x,int y)
{
    
    // If the current node has a value, it does not need to be filled , Skip directly to the next node 
    if(a[x][y]!=0)
        if(x==N-1&&y==N-1) pr();// All filled 
        else if(y==N-1) dfs(x+1,1);//x The row has been filled 
        else dfs(x,y+1);//x Row by row, column by column 
    else
        for(int i=1;i<N;i++)
        {
    
            // Judge that the current node already has a value i, There is no execution fill 
            if(!row[x][i]&&!col[y][i]&&!g[((x-1)/3)*3+(y-1)/3+1][i])
            {
    
                // Filling operation , Mark the state of the point 
                a[x][y]=i,row[x][i]=1,col[y][i]=1,g[((x-1)/3)*3+(y-1)/3+1][i]=1;
                if(x==N-1&&y==N-1) pr();// When the point is filled, the graph is filled 
                else if(y==N-1) dfs(x+1,1);// Operate on the next point after filling 
                else dfs(x,y+1);
                // to flash back , State restoration 
                a[x][y]=0,row[x][i]=0,col[y][i]=0,g[((x-1)/3)*3+(y-1)/3+1][i]=0;
            }
        }
}
int main()
{
    
    char temp;
    for(int i=1;i<N;i++)
        for(int j=1;j<N;j++)
        {
    
            cin>>temp;
            // For the input char Data storage 、1-9 Corresponding to 1-9,'.' Corresponding to 0
            a[i][j]=temp>='0'&&temp<='9'?int(temp-'0'):0;
            // The label is not 0 Point situation of 
            if(a[i][j]) g[((i-1)/3)*3+(j-1)/3+1][a[i][j]]=1,row[i][a[i][j]]=1,col[j][a[i][j]]=1;
        }
    // from 1,1 Start sequential search , Search line by line from left to right 
    dfs(1,1);
    return 0;
}

Of course , So violent , For more difficult data , It must be TLE Of , Then we need to optimize the code , It is divided into the following aspects ：
1、 Select more than filled ( That's ok 、 Both column and square matrix satisfy ) As the starting point of filling
2、 Prune properly , For branches that do not need to continue , No more execution
3、 Use bit operation to improve operation speed

Above, Simple Sudoku This topic oj Last run time , After optimization, we can say that it is a fast batch ！！！ The optimized code can submit this topic ： Advanced Sudoku , The data is difficult ( The optimized code has run in the advanced version of Sudoku 600+ms), If you are interested, you can try , I have passed this title , After that, I will release a detailed explanation , Attach first AC Code , If you are interested in children's shoes, you can have a look first .

#include<iostream>
#include<algorithm>
using namespace std;
const int N=9;
char str[100];
int row[N],col[N],chunk[3][3],tab[1<<N],map[1<<N];
inline int lowbit(int x)
{
    
    return x&-x;
}
inline void init()
{
    
    for(int i=0;i<N;i++) row[i]=col[i]=(1<<N)-1;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            chunk[i][j]=(1<<N)-1;
}
inline int get(int x,int y)
{
    
    return row[x]&col[y]&chunk[x/3][y/3];
}
bool dfs(int cnt)
{
    
    if(!cnt) return true;
    int x,y,mmin=10,t;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(str[i*9+j]=='.')
            {
    
                t=tab[get(i,j)];
                if(t<mmin) mmin=t,x=i,y=j;
            }
    for(int i=get(x,y);i;i-=lowbit(i))
    {
    
        t=map[lowbit(i)];
        row[x]-=1<<t;
        col[y]-=1<<t;
        chunk[x/3][y/3]-=1<<t;
        str[x*9+y]='1'+t;
        if(dfs(cnt-1)) return true;
        row[x]+=1<<t;
        col[y]+=1<<t;
        chunk[x/3][y/3]+=1<<t;
        str[x*9+y]='.';
    }
    return false;
}
int main()
{
    
    for(int i=0;i<N;i++) map[1<<i]=i;
    for(int i=0;i<1<<N;i++)
    {
    
        int s=0;
        for(int j=i;j;j-=lowbit(j)) s++;
        tab[i]=s;
    }
    for(int i=0;i<N*N;i++) cin>>str[i];
    init();
    int cnt=0;
    for(int i=0,k=0;i<N;i++)
        for(int j=0;j<N;j++,k++)
            if(str[k]!='.')
            {
    
                int t=str[k]-'1';
                row[i]-=1<<t;
                col[j]-=1<<t;
                chunk[i/3][j/3]-=1<<t;
            }
            else cnt++;
    dfs(cnt);
    for(int i=0;i<N;i++)
    {
    
        for(int j=0;j<N;j++)
            printf("%c",str[i*N+j]);
        puts("");
    }
    return 0;
}