首先是最简单的数独问题:题目链接(数独的规则是每行每列,每个3 × 3的九宫格内数字1~9均恰好出现一次,如果还有疑惑可以自行百度)
当然我们把题目再简化一点,每次的测试样例只有一个数独,按9*9无换行的形式输入测试样例,输入输出如下:
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
输入为9×9的数据。一共9行,每行有9个数字。数字为0表示对应的数字盘为空。
输出:对于每个测试用例,程序应以与输入数据相同的格式打印解决方案(9×9)。空单元格必须根据规则进行填充。如果解决方案不是唯一的,则程序可以打印其中任何一种。
接下来尝试用深搜来解决问题,当然我们只是单纯的深搜,先不做其他优化:
1.我们先将数独输入,定义一个char类型的全局变量数组s[10][10],通过二重循环cin读入数据,可以在main函数开头加上cin.tie(0)进行优化,然后我们定义三个bool类型的辅助判断二维数组,就命名为vx[10][10],vy[10][10]和vv[10][10],这三个二维数组作为全局变量。我们先展示一下代码,再解释这三个辅助数组的含义:
#include<bits/stdc++.h>
using namespace std;
char s[10][10];
bool vx[10][10],vy[10][10],vv[10][10];
bool f;
int main()
{
cin.tie(0);
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
cin>>s[i][j];
}
for(int i=1;i<9;i++)
for(int j=0;j<9;j++)
{
if(s[i][j]!='0'){
vx[i][s[i][j]-'0']=true;
vy[j][s[i][j]-'0']=true;
vv[i/3*3+j/3][s[i][j]-'0']=true;
}
}
dfs(0,0);
return 0;
}
2.可以看到我们读入数据后又做了一个二重循环,用到了三个辅助判断的二维数组,这三个数组中vx用来记录每一行哪些数不可以填,vy用来记录每一列哪些数不可以填,vv用来记录每个九宫格哪些数不可以填,实际上vv数组将数独分成了按自左向右,自上向下的0-8个小的九宫格。因为全局变量的二维bool数组开始全为false,我们将其改为true后代表某行某列某个小九宫格的数是不能再用的。(注:f这个全局变量用在dfs函数里)
3.好,前面都是一些准备工作,我们接下来做dfs深度优先搜索,还是先看一下dfs这个被调用的深搜函数的代码:
void dfs(int x,int y)
{
if(f) return;
if(x==9)
{
f=true;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
if(j!=8)
{
cout<<s[i][j];
}
else
{
cout<<s[i][j]<<endl;
}
}
return;
}
if(y==9) //如果到了行末,换行搜索
{
dfs(x+1,0);
return;
}
if(s[x][y]!='0') //如果该空已经有了数字,不用填,向下一个空格搜索
{
dfs(x,y+1);
return;
}
for(int i=1;i<=9;i++)
{
if(!vx[x][i]&&!vy[y][i]&&!vv[x/3*3+y/3][i]){
s[x][y]='0'+i;
vx[x][i]=true;
vy[y][i]=true;
vv[x/3*3+y/3][i]=true;
dfs(x,y+1);
vx[x][i]=false;
vy[y][i]=false;
vv[x/3*3+y/3][i]=false;
s[x][y]='0';
}
}
}
深搜是自上往下,自左往右的方式开始搜索,首先如果搜到第九行了,(注意我们数据是存在0-8行)我们这个数独明显被解决了,将全局变量f改为true,直接输出数据,判断f,然后退出dfs函数。然后具体搜索的逻辑也很简单了,如果搜到了某一行的末尾,我们就换行搜索,如果某空格已经填过了,向下一个空格搜索,如果某个空格可填,从1-9开始,依次尝试,之前的三个辅助判断数组用于判断某个数字能否填入该空格,填入后修改辅助数组和空格内容继续搜索下一个空格,然后注意如果后续走不通的话你还是要回来的,所以将改动的内容再改回去,这样整个搜索函数就完成了。最后看一下整体的源代码:
#include<bits/stdc++.h>
using namespace std;
char s[10][10];
bool vx[10][10],vy[10][10],vv[10][10];
bool f;
void dfs(int x,int y)
{
if(f) return;
if(x==9)
{
f=true;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
if(j!=8)
{
cout<<s[i][j];
}
else
{
cout<<s[i][j]<<endl;
}
}
return;
}
if(y==9)
{
dfs(x+1,0);
return;
}
if(s[x][y]!='0')
{
dfs(x,y+1);
return;
}
for(int i=1;i<=9;i++)
{
if(!vx[x][i]&&!vy[y][i]&&!vv[x/3*3+y/3][i]){
s[x][y]='0'+i;
vx[x][i]=true;
vy[y][i]=true;
vv[x/3*3+y/3][i]=true;
dfs(x,y+1);
vx[x][i]=false;
vy[y][i]=false;
vv[x/3*3+y/3][i]=false;
s[x][y]='0';
}
}
}
int main()
{
cin.tie(0);
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
cin>>s[i][j];
}
for(int i=1;i<9;i++)
for(int j=0;j<9;j++)
{
if(s[i][j]!='0'){
vx[i][s[i][j]-'0']=true;
vy[j][s[i][j]-'0']=true;
vv[i/3*3+j/3][s[i][j]-'0']=true;
}
}
dfs(0,0);
return 0;
}
代码已经编译并测试通过了,你可以自己尝试在电脑上复制代码后输入一组测试数据试一下。
但是代码运行时间还是超时了,这个题是算法竞赛上的题目,时间限制很高,要压缩到1s以内,所以还要做优化。