首先是最简单的数独问题：题目链接（数独的规则是每行每列，每个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以内，所以还要做优化。