欢迎去ZJYYCOJ试试
题目
芬兰数学家因卡拉，花费3个月时间设计出了世界上迄今难度最大的数独游戏，而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。这是英国《每日邮报》2012年6月30日的一篇报道。
作为Acmer的你，能写一个程序解决所有的数独问题吗？
世界上迄今难度最大的数独游戏：
输入
本题包含多组测试。每组测试会给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，问号（?）表示需要你填的数。
输出
对于每组测试，请输出它的解，同一行相邻的两个数用一个空格分开。两组解之间要一个空行。 如果有多种答案，输出任意一种即可!
输入样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| ? 2 6 7 ? ? 5 1 8
7 3 1 ? 5 8 6 2 4
5 4 ? 2 6 1 3 9 7
6 ? 4 3 7 ? ? 8 1
2 8 7 1 9 6 4 3 5
1 9 ? ? 8 4 7 6 2
3 7 ? 8 ? 9 1 4 6
8 ? 9 4 1 5 2 7 3
? 1 2 6 3 7 8 5 9
? 2 6 7 ? ? 5 1 8
7 3 1 ? 5 8 6 2 4
5 4 ? 2 6 1 3 9 7
6 ? 4 3 7 ? ? 8 1
2 8 7 1 9 6 4 3 5
1 9 ? ? 8 4 7 6 2
3 7 ? 8 ? 9 1 4 6
8 ? 9 4 1 5 2 7 3
? 1 2 6 3 7 8 5 9
|
输出样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 9 2 6 7 4 3 5 1 8
7 3 1 9 5 8 6 2 4
5 4 8 2 6 1 3 9 7
6 5 4 3 7 2 9 8 1
2 8 7 1 9 6 4 3 5
1 9 3 5 8 4 7 6 2
3 7 5 8 2 9 1 4 6
8 6 9 4 1 5 2 7 3
4 1 2 6 3 7 8 5 9
9 2 6 7 4 3 5 1 8
7 3 1 9 5 8 6 2 4
5 4 8 2 6 1 3 9 7
6 5 4 3 7 2 9 8 1
2 8 7 1 9 6 4 3 5
1 9 3 5 8 4 7 6 2
3 7 5 8 2 9 1 4 6
8 6 9 4 1 5 2 7 3
4 1 2 6 3 7 8 5 9
|
代码
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
| #include<bits/stdc++.h>
using namespace std;
int m,a,b,sum,flag;
char Map[20][20],n;
void print(){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(j==0)
printf("%c",Map[i][j]);
else
printf(" %c",Map[i][j]);
}
printf("\n");
}
printf("\n");
}
bool check(int x,int y,char k){
for(int i=0;i<9;i++){
if(Map[i][y]==k||Map[x][i]==k)
return false;
}
int x1=x/3*3;
int y1=y/3*3;
for(int i=x1;i<x1+3;i++){
for(int j=y1;j<y1+3;j++){
if(Map[i][j]==k){
return false;
}
}
}
return true;
}
void dfs(int x,int y){
if(x==9&&y==0){
flag=1;
print();
return;
}
if(Map[x][y]!='?'){
if(y==8)
dfs(x+1,0);
else
dfs(x,y+1);
}
else{
for(int i=1;i<=9;i++){
if(check(x,y,i+'0')){
Map[x][y]=i+'0';
if(y==8){
dfs(x+1,0);
}
else{
dfs(x,y+1);
}
if(flag==1)
return;
Map[x][y]='?';
}
}
}
}
int main(){
while(cin>>n){
Map[0][0]=n;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(i==0&&j==0){
continue;
}
cin>>Map[i][j];
}
}
flag=0;
dfs(0,0);
}
return 0;
}
|