题目链接
P1784 数独
题目描述
数独是根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。
芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。
这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。
据介绍，目前数独游戏的难度的等级有一道五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。

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

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

数独人做的话是要靠数学逻辑，那么用计算机直接暴力枚举所有的可能，找到答案后就输出并退出，否则就一直找，那么DFS就非常合适。
我们用三个二维数组分别代表行，列，格
其中对于格来说，从1—9格，通过数学计算找规律 发现每过3列，方阵的序号+1，每过3行，方阵的序号+3。
于是我们有了这样的表达式：

方阵序号=（行数-1）/3*3+（列数-1）/3+1

二维数组第一维表示行（列，格），第二维表示要试的这个数，然后暴力跑，一行一行地填，把所有可能行全部试一遍就好
然后就是极其简单的代码啦

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=10;
int a[N][N];
bool line[N][N],lis[N][N],grid[N][N];
void print()//输出数独
{
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    exit(0);//安全退出
}
void dfs(int x,int y)
{
    if(a[x][y]!=0)
    {
        if(x==9&&y==9)
            print();
        if(y==9)
            dfs(x+1,1);
        else dfs(x,y+1);
    }
    else
    {
        for(int i=1;i<=9;i++)
        {
            if(!line[x][i]&&!lis[y][i]&&!grid[(x-1)/3*3+(y-1)/3+1][i])
            {
                a[x][y]=i;
                line[x][i]=true;
                lis[y][i]=true;
                grid[(x-1)/3*3+(y-1)/3+1][i]=true;
                if(x==9&&y==9)
                    print();
                if(y==9)
                    dfs(x+1,1);
                else dfs(x,y+1);
                a[x][y]=0;
                line[x][i]=false;
                lis[y][i]=false;
                grid[(x-1)/3*3+(y-1)/3+1][i]=false;
            }
        }
    }
}
int main()
{

    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            cin>>a[i][j];
            if(a[i][j]>0)
            {
                line[i][a[i][j]]=true;
                lis[j][a[i][j]]=true;
                grid[(i-1)/3*3+(j-1)/3+1][a[i][j]]=true;
            }
        }
    }
    dfs(1,1);
}

有任何疑问欢迎评论哦虽然我真的很菜