题目描述
数独是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得图中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入共 9 行，每行包含一个长度为 9 的字符串，用来表示数独矩阵。
其中的每个字符都是 1∼9 或 .（表示尚未填充）。
输出格式
输出补全后的数独矩阵。
数据保证有唯一解。
输入样例：
.2738..1.
.1...6735
.......29
3.5692.8.
.........
.6.1745.3
64.......
9518...7.
.8..6534.
输出样例：
527389416
819426735
436751829
375692184
194538267
268174593
643217958
951843672
782965341
算法
Dfs深搜和很少很少......（此处省略无数个很少)的模拟
废话不多说，直接上代码（我是不会说这是我的第五篇题解的）
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
char s;//定义
int a[10][10];
int h[10][10],l[10][10],g[10][10];
void print()//输出函数
{
for(int i=1;i<=9;i++)//把每个点输出
{
for(int j=1;j<=9;j++) cout<<a[i][j];
cout<<endl;
}
return ;//结束
}
void dfs(int x,int y)//深搜函数
{
if(a[x][y]!=0){//当前格中有数就直接跳过
if(x==9&&y==9) print();//要是搜索完了就输出
if(y==9) dfs(x+1,1);//一列搜完列就变成1，行就加一，以此递归
else dfs(x,y+1);//否则递归该行的下一列
}
if(a[x][y]==0){//没有数时
for(int i=1;i<=9;i++){//循环
if(h[x][i]==0&&l[y][i]==0&&g[(x-1)/3*3+(y-1)/3+1][i]==0){//如果没打标记
a[x][y]=i;//存数
h[x][i]=1;//打标记
l[y][i]=1;
g[(x-1)/3*3+(y-1)/3+1][i]=1;//这样写可以解决大格子中的小格子可能不在同一行，列的问题
if(x==9&&y==9) print();
if(y==9) dfs(x+1,1);
else dfs(x,y+1);
a[x][y]=0;//恢复现场
h[x][i]=0;
l[y][i]=0;
g[(x-1)/3*3+(y-1)/3+1][i]=0;
}
}
}
}
int main()
{
for(int i=1;i<=9;i++){//循环遍历
for(int j=1;j<=9;j++){
cin>>s;//输入
if(s=='.') a[i][j]=0;//处理成数字
else a[i][j]=s-48;
if(a[i][j]!=0){//格子上有数就打标记
h[i][a[i][j]]=1;
l[j][a[i][j]]=1;
g[(i-1)/3*3+(j-1)/3+1][a[i][j]]=1;
}
}
}
dfs(1,1);//开始递归
return 0;
}
