最近学校搞了个数独比赛，于是找了这道题。
题目描述
数独是根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。
芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。
这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。
据介绍，目前数独游戏的难度的等级有一道五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。
输入输出格式
输入格式：
一个未填的数独
输出格式：
填好的数独
输入输出样例
输入样例#1：
8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0
输出样例#1：
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
题解：
这是一道深度优先搜索题，obviously!!
只要开3个BOOL数组，hang[i][j]（第i行是否出现过数j）,lie[i][j]（第i列是否出现过数j）,kuai[i][j]（第i块是否出现过数j）。
其中你要自己推一个(x,y)属于哪一块的公式： f(x,y) = (x-1)/3*3+ceil(y/3.0) 或者 f(x,y) = (x-1)/3*3+(y-1)/3+1 （从左往右，从上向下数）
所以这道题的标程就很简单了：
#include<bits/stdc++.h>
using namespace std;
int Map[15][15];
bool hang[10][10],lie[10][10],kuai[10][10],f = 0;
void print()
{
for (int i = 1 ; i <= 9 ; i++)
{
for (int j = 1 ; j <= 8 ; j ++) printf("%d ",Map[i][j]);
cout<<Map[i][9]<<endl;
}
}
void dfs(int x,int y)
{
if (Map[x][y] != 0)
{
if (x == 9 && y == 9) {
print();
f = 1;
return;
}
if (y == 9) dfs(x+1,1); else dfs(x,y+1);
}
if (Map[x][y] == 0)
for (int i = 1 ; i <= 9 ; i ++)
{
if (hang[x][i] && lie[y][i] && kuai[(x-1)/3*3+(y-1)/3+1][i])
{
Map[x][y] = i; int k = (x-1)/3*3+(y-1)/3+1;
hang[x][i] = 0;
lie[y][i] = 0;
kuai[k][i] = 0;
if (x == 9 && y == 9) {
print();
f = 1;
return;
}
if (y == 9) dfs(x+1,1); else dfs(x,y+1);
if (f) return;
Map[x][y] = 0;
hang[x][i] = 1;
lie[y][i] = 1;
kuai[k][i] = 1;
}
}
}
int main()
{
memset(hang,true,sizeof(hang));
memset(lie,true,sizeof(lie));
memset(kuai,true,sizeof(kuai));
for (int i = 1 ; i <= 9 ; i ++)
for (int j = 1 ; j <= 9 ; j ++)
{
scanf("%d",&Map[i][j]);
if (Map[i][j] > 0)
{
int k = (i-1)/3*3+(j-1)/3+1;
hang[i][Map[i][j]] = 0;
lie[j][Map[i][j]] = 0;
kuai[k][Map[i][j]] = 0;
}
}
dfs(1,1);
return 0;
}
