http://poj.org/problem?id=2676
深搜的题目。
题意呢就是一个数独的游戏，应该都知道规则。
思路：我的思路很简单，就是用数组来判断某个数字是否可以使用，而每一个数字都由三个条件来限制它，分别是行和列，和其所在的9宫格里面，是不能有重复的。
如果有重复的，则不能使用，甚至都不能尝试。
代码写的也比较渣。还有这个题的数据应该不深，从0，0搜和从8，8开始搜，时间差距非常大，我的从0，0开始是1200Ms,从8，8是16Ms.
这是数据的问题。
#include <stdio.h>
#include <string.h> int sodu[][],flog; char a[][]; bool h[][],s[][],cube[][]; //h代表行，s代表列，cube代表数字所在的的是哪一个9宫格。 int jud(int x) //用来判断数字是在哪一个9宫格，我的分区是按从0 1 2/3 4 5/6 7 8来分的。
{
if(x>=&&x<) return ;
if(x>=) return ;
return ;
} void bfs(int x,int y)
{
for(int q=;q>=;q--) //这个是来判断是否搜索成功。
{
flog=;
for(int p=;p>=;p--)
{
if(sodu[q][p]==) {flog=;break;}
if(flog&&p==&&q==) flog=;
}
if(flog==) break;
}
for(int i=;i>=&&flog;i--)
for(int j=;j>=;j--)
{
if(sodu[i][j]==)
{
for(int k=;k<;k++)
{
if(h[i][k]&&s[j][k]&&cube[j/+jud(i)][k])
{
sodu[i][j]=k;
h[i][k]=false;
s[j][k]=false;
cube[j/+jud(i)][k]=false;
bfs(,);
if(flog==)return;
h[i][k]=true;
s[j][k]=true;
cube[j/+jud(i)][k]=true;
}
}
sodu[i][j]=; //这里记得要归0，不然回溯的时候，下一次不会再这个数值。
if(sodu[i][j]==)return;
}
}
} int main()
{
int n;
scanf("%d",&n);
while(n--)
{
for(int i=;i<;i++)
scanf("%s",a[i]);
for(int i=;i<;i++)
for(int j=;j<;j++)
sodu[i][j]=a[i][j]-'';
memset(h,true,sizeof(h));
memset(s,true,sizeof(s));
memset(cube,true,sizeof(cube));
for(int i=;i<;i++)
for(int j=;j<;j++)
{
if(sodu[i][j]!=)
{
h[i][sodu[i][j]]=false;
s[j][sodu[i][j]]=false;
cube[j/+jud(i)][sodu[i][j]]=false;
}
}
flog=;
bfs(,);
for(int i=;i<;i++)
{
for(int j=;j<;j++)
printf("%d",sodu[i][j]);
printf("\n");
} }
return ;
}