POJ中有四道数独题，链接如下。
难度大致为：2676=2918<3074<3076
http://poj.org/problem?id=2676
http://poj.org/problem?id=2918
http://poj.org/problem?id=3074
http://poj.org/problem?id=3076
首先我们先来讲讲2676和2918这两道最简单的吧。
想法1：因为是数独题，所以每行每列以及每个小方块的数字是不能重复的。因此我们可以用DFS尝试填数字上去。
然后再加一些适当的剪枝就能AC 2676和2918题了。
以下给出2918的AC代码。 2918和2676只是输出格式不一样。改一下就能AC了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
using namespace std;
int T;
int tri[9][9];
bool row[9][9];
bool col[9][9];
bool little_tri[9][9];
int cnt=1;
int No(int i,int j){ //判断当前格子是属于哪个小方格的
return (i/3)*3+j/3;
}
bool dfs(int i,int j){
if(i==9){ //出口
return true;
}
int no=No(i,j);
int temp=tri[i][j];
bool flag;
if(temp){ //如果该格子有数字就直接dfs下一个格子
if(j==8){
flag= dfs(i+1,0);
}
else{
flag= dfs(i,j+1);
}
if(flag)
return true;
else
return false;
}
else{
for(int k=1;k<=9;k++){ //尝试1~9的数字
if(!row[i][k-1]&&!col[j][k-1]&&!little_tri[no][k-1]){ //前提是该格子允许填入k这个数字
tri[i][j]=k;
row[i][k-1]=1;
col[j][k-1]=1;
little_tri[no][k-1]=1;
if(j==8){
flag= dfs(i+1,0);
}
else{
flag= dfs(i,j+1);
}
if(flag)
return true;
else { //如果失败了，则回溯！
tri[i][j]=0;
row[i][k-1]=0;
col[j][k-1]=0;
little_tri[no][k-1]=0;
}
}
}
}
return false;
}
void solve(){
string a;
memset(tri,0,sizeof(tri));
memset(row,0,sizeof(row));
memset(col,0,sizeof(col));
memset(little_tri,0,sizeof(little_tri));
int tep;
int no;
for(int i=0;i<9;i++){
cin>>a;
for(int j=0;j<9;j++){
tri[i][j]=a[j]-'0';
tep=tri[i][j];
no=No(i,j);
if(tep){
row[i][tep-1]=1;
col[j][tep-1]=1;
little_tri[no][tep-1]=1;
}
}
}
dfs(0,0);
printf("Scenario #%d:\n",cnt++);
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
cout<<tri[i][j];
}
cout<<endl;
}
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
scanf("%d",&T);
while(T--){
solve();
if(T!=0)cout<<endl;
}
return 0;
}
但这个算法是无法通过POJ3074的，因为3074题的空白格子比较多，该方法行不通，需要进一步优化。
现在讲一下POJ3074的思路
想法2：考虑处理某一行时，对于某个还没有用过的数字，如果该行只有一个可行的空白格子，则将该数字填入该格子。
对于列和方块也一样。
反之，如果某个格子可填的数字只有一个，也只能将该数字填入该格子。
POJ3076的思路
想法3：
假设有一个只有两个候选数字的格子，如果选择其中一个产生了矛盾，那么就可以确定选择另一个。而对于有五个候选数字的格子，即使其中一个出现了矛盾，依然还有四个候选数字需要尝试。换句话说，选数字少的格子填数字比从左上角开始DFS更加高效.。
由于今晚比较晚了，下次有空补上 3074 和3076的代码。