题解 P1784 【数独】

· · 题解

我来凑热闹了OvO

其实我刷完这道题的时候，看到有一些DALAO做的方法差不多哎，但是都不是很详细，一部分人可能看不懂哦..。 所以，我写的以下题解会超多，做好心理准备吧。QWQ

数独规则（懂规则的可以跳过）

按照百度上的说法是这样子的：

数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3×3）内的数字均含1-9，不重复。

如上图

重点部分我都用黑体标出来了。规则是这样的，虽然数独是需要逻辑推算的，但是对于计算机来说，就直接枚举每个格子的可能性就可以了（真暴力...）。那么我们如何通过程序实现呢？

判断重复

数独要求每一行、每一列、每一个3×3方阵内的数字，不重复。

行和列重复判断是相当简单的。我们可以定义两个bool型二维数组，当此行（或列）填充数字时，我们可以直接把这行的这个数字打上true表示有数字了。

//譬如第一行第三列填入数字2
bool p[][],l[][];//p:行,l:列;
p[1][2]=l[3][2]=true;

如果后面再填充数字，就判断此行（或列）是否填过这个数字即可。

重点：判断方阵中数字重复

如果判断方阵中数字重复？怎样用行列来表示是几方阵成了个问题。但是不用怕，我们有van能的数学。

观察下面这个数独：

可以看到，每过3列，方阵的序号+1，每过3行，方阵的序号+3。

于是我们有了这样的表达式：


方阵序号=（行数-1）/3*3+（列数-1）/3+1
//注意！行数列数要-1，因为3的整数倍数/3会比原方阵大1，不能满足上述需求。

如果填充了数字，就用这个表达式把相应方阵的相应数字打上true标记就可以了。

有了上述方法，就可以写个深搜函数来解决问题了！

至于剩下的，代码里批注讲哦！上代码！

//stone_juice P1784 数独 
#include <bits/stdc++.h>//华丽的开头~ 
using namespace std;
int sd[11][11];//数独方阵定义 
bool p[11][11],l[11][11],fz[11][11];//行（排？），列，方阵。 
void _out()//优美地输出~ 
{
    for(int i=1;i<=9;i++)
    {   
        for(int j=1;j<=9;j++)
            cout<<sd[i][j]<<" ";
        cout<<endl;
    }
    exit(0);//注意，此处要用exit(0)。用return的话不会退出dfs函数，会增加运算量。 
}
void dfs(int x,int y)//神奇的深搜~
{
    if(sd[x][y]!=0)//如果原来这个位置有数字，跳过。 
        if(x==9&&y==9)_out();//当行列都为9，填充完成，输出~
        else if(y==9)dfs(x+1,1);//当列数为9，搜索下一排。 
        else dfs(x,y+1);//搜下一列啦~ 
    else//原来的地方没有数字，准备填充！ 
        for(int i=1;i<=9;i++)
            if((!p[x][i])&&(!l[y][i])&&(!fz[(x-1)/3*3+(y-1)/3+1][i]))
            //判断是不是重复了。方法题解有讲！ 
            {
                sd[x][y]=i;//填充！ 
                p[x][i]=l[y][i]=fz[(x-1)/3*3+(y-1)/3+1][i]=true;//打上标记。 
                if(x==9&&y==9)_out();//全部填完！输出~ 
                else if(y==9)dfs(x+1,1);//同上！搜下一行。
                else dfs(x,y+1);//搜下一列！ 
                sd[x][y]=0; //恢复标记。 
                p[x][i]=l[y][i]=fz[(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++)
        {
            int t;//定义tmp（防止下面代码太长？） 
            cin>>t;//炫酷地输入 
            if(t!=0)
                p[i][t]=l[j][t]=fz[(i-1)/3*3+(j-1)/3+1][t]=true;
            //填充的不是0的话，表示原来有数字了。打上标记。   
            sd[i][j]=t;//填充进数独。 
        }   
    dfs(1,1);//搜搜搜！ 
    return 0;//完美地结束~ 
}

虽然我的方法不是最优解，但是看我写的这么认真，各位DALAO给个赞呗！祝愿你们早日AC!!

#include <致管理员：我不小心把图弄挂了...请重新审核一下吧谢谢QWQ>