在我的不断探索发现下，我意识到 DFS 似乎可以用来做数独……

于是乎就上手操作了一下，然后就做出来了？

其实思路很简单，就是简单的 DFS

(废话，本蒟蒻都想出来了能不简单吗)

就是模仿人填数独的过程，只是更加无脑。

一个个试起走，放不了就回溯，直到解出答案，输出

真的就只有那么简单了，秒杀人脑啊有没有

上干货！

Step.1 通过 judge 判断是否合法

bool judge(int now)
{
    int row = now / 9;
    //当前行
    int col = now % 9;
    //当前列
    int j;
    for(j = 0; j < 9; ++j)
    {
        if(maap[row][j] == maap[row][col] && j != col)
        {
            return false;
        }
    }//这是检查同一行中的重复
    for(j = 0; j < 9; ++j)
    {
        if(maap[j][col] == maap[row][col] && j != row)
        {
            return false;
        }
    }//这是检查同一列中的重复
    int tmp_row = row / 3 * 3;
    int tmp_col = col / 3 * 3;
    for(j = tmp_row; j < tmp_row + 3;++j)
    {
        for(int k = tmp_col; k < tmp_row + 3; ++k)
        {
            if(maap[j][k] == maap[row][col] && j != row && k != col)
            {
                return false;
            }
        }
    }//这是检查同一 3*3 小格中的重复
    //经过三个判断如果可以放那么则返回真
    return true;
}

Step.2 利用 flowback 回溯

void flowback(int now)
{
    if(now == 81)
    {
        print_map();
        return;
    }//输出
    int row = now / 9;
    int col = now % 9;
    if(!vis[row][col])
    {
        for(int i = 1; i <= 9; ++i)
        {
            vis[row][col]=true;
            maap[row][col] = i;//赋值
            if(judge(now))
            {//可以放
                flowback(now+1);//进入下一层
            }
        }
        vis[row][col]=false;//回溯
    }
    else
    {
        flowback(now+1);
    }
}

Step.3 轻松愉快的输出 print_map

void print_map()
{
        for(int i = 0; i < 9; ++i)
        {
            for(int j =  0; j < 9; ++j)
            {
                cout<<maap[i][j]<<" ";
            }
            cout<<endl;
        }
}

其实就是很简单的回溯，判重也超级简单，只是有可能跑得比较慢鹅已……

最后还是良心的上个全代码，也请巨佬们在时间复杂度优化上加以指导！

#include <bits/stdc++.h>
using namespace std;
int maap[9][9];
bool vis[9][9];
bool judge(int now)
{
    int row = now / 9;
    //当前行
    int col = now % 9;
    //当前列
    int j;
    //同一行
    for(j = 0; j < 9; ++j)
    {
        if(maap[row][j] == maap[row][col] && j != col)
        {
            return false;
        }
    }
    //同一列
    for(j = 0; j < 9; ++j)
    {
        if(maap[j][col] == maap[row][col] && j != row)
        {
            return false;
        }
    }
    //同一小格
    int tmp_row = row / 3 * 3;
    int tmp_col = col / 3 * 3;
    for(j = tmp_row; j < tmp_row + 3;++j)
    {
        for(int k = tmp_col; k < tmp_row + 3; ++k)
        {
            if(maap[j][k] == maap[row][col] && j != row && k != col)
            {
                return false;
            }
        }
    }
    //经过三个判断如果可以放那么则真的可以了
    return true;
}
void print_map()
{
        for(int i = 0; i < 9; ++i)
        {
            for(int j =  0; j < 9; ++j)
            {
                cout<<maap[i][j]<<" ";
            }
            cout<<endl;
        }
}
void flowback(int now)
{
    if(now == 81)
    {
        print_map();
        return;
    }
    int row = now / 9;
    int col = now % 9;
    if(!vis[row][col])
    {
        for(int i = 1; i <= 9; ++i)
        {
            vis[row][col]=true;
            maap[row][col] = i;//赋值
            if(judge(now))
            {//可以放
                flowback(now+1);//进入下一层
            }
        }
        vis[row][col]=false;//回溯
    }
    else
    {
        flowback(now+1);
    }
}
int main()
{
    for(int i = 0; i < 9; ++i)
    {
        for(int j = 0; j < 9; ++j)
        {
            cin>>maap[i][j];
            if(maap[i][j])
            {
                vis[i][j]=true;
                //有数的地方就不自己放了
            }
        }
    }
    flowback(0);
    //从第 0 个数开始回溯
    return 0;
}

#2

#include <bits/stdc++.h>
#define ri register int
using namespace std;
int maap[9][9];
int flg=0;
int num=0;

int read()
{
    int num=0;
    int flg=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
        {
            flg=-1;
        }
        c=getchar();
    }
    while(isdigit(c))
    {
        num=(num<<1)+(num<<3)+(c^48);
        c=getchar();
    }
    return num*flg;
}

void print_map()
{
    printf("Scenario #%d:\n",++num);
    for(ri i=0;i<9;i++)
    {
        for(ri j=0;j<9;j++)
        {
            printf("%d",maap[i][j]);
        }
        printf("\n");
    }
}
bool judge(int x,int y,int k)
{
    for(ri i=0;i<9;i++)
    {
        if(maap[i][y]==k||maap[x][i]==k)
        {
            return 0;
        }
    }
    int x1=x/3*3;
    int y1=y/3*3;
    for(ri i=x1;i<x1+3;i++)
    {
        for(ri j=y1;j<y1+3;j++)
        {
            if(maap[i][j]==k)
            {
                return 0;
            }
        }
    }
    return 1;
}
void dfs(int x,int y)
{
    if(x==9&&y==0)
    {
        print_map();
        flg=1;
        return ;
    }
    if(maap[x][y]!=0)
    {
        if(y==8)
        {
            dfs(x+1,0);
        }
        else
        {
            dfs(x,y+1);
        }
    }
    else
    {
        for(ri i=1;i<=9;i++)
        {
            if(judge(x,y,i)!=0)
            {
                maap[x][y]=i;
                if(y==8)
                {
                    dfs(x+1,0);
                }
                else
                {
                    dfs(x,y+1);
                }
                if(flg==1)
                return ;
                maap[x][y]=0;
            }
        }
    }
}
int main()
{
    int t=read();
    while(t--)
    {
        memset(maap,0,sizeof(maap));
        for(ri i=0;i<9;i++)
        {
            for(ri j=0;j<9;j++)
            {
                scanf("%1d",&maap[i][j]);
            }
        }
        flg=0;//判断是否继续 dfs
        dfs(0,0);
    }
    return 0;
}
/*
2
000000000
817965430
652743190
175439820
308102950
294856370
581697240
903504610
746321580

781654392
962837154
543219786
439182675
158976423
627543918
316728549
895461237
274395861
*/

撒花✿✿ヽ(°▽°)ノ✿