Life has its own fate, and meeting may not be accidental.

0%

数独游戏-DFS

欢迎去ZJYYCOJ试试

题目

芬兰数学家因卡拉,花费3个月时间设计出了世界上迄今难度最大的数独游戏,而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。这是英国《每日邮报》2012年6月30日的一篇报道。
作为Acmer的你,能写一个程序解决所有的数独问题吗?

世界上迄今难度最大的数独游戏:

输入

本题包含多组测试。每组测试会给你一个 9*9 的矩阵,同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数,问号(?)表示需要你填的数。

输出

对于每组测试,请输出它的解,同一行相邻的两个数用一个空格分开。两组解之间要一个空行。 如果有多种答案,输出任意一种即可!

输入样例

1
? 2 6 7 ? ? 5 1 8
2
7 3 1 ? 5 8 6 2 4
3
5 4 ? 2 6 1 3 9 7
4
6 ? 4 3 7 ? ? 8 1
5
2 8 7 1 9 6 4 3 5
6
1 9 ? ? 8 4 7 6 2
7
3 7 ? 8 ? 9 1 4 6
8
8 ? 9 4 1 5 2 7 3
9
? 1 2 6 3 7 8 5 9
10
? 2 6 7 ? ? 5 1 8
11
7 3 1 ? 5 8 6 2 4
12
5 4 ? 2 6 1 3 9 7
13
6 ? 4 3 7 ? ? 8 1
14
2 8 7 1 9 6 4 3 5
15
1 9 ? ? 8 4 7 6 2
16
3 7 ? 8 ? 9 1 4 6
17
8 ? 9 4 1 5 2 7 3
18
? 1 2 6 3 7 8 5 9

输出样例

1
9 2 6 7 4 3 5 1 8
2
7 3 1 9 5 8 6 2 4
3
5 4 8 2 6 1 3 9 7
4
6 5 4 3 7 2 9 8 1
5
2 8 7 1 9 6 4 3 5
6
1 9 3 5 8 4 7 6 2
7
3 7 5 8 2 9 1 4 6
8
8 6 9 4 1 5 2 7 3
9
4 1 2 6 3 7 8 5 9
10
11
9 2 6 7 4 3 5 1 8
12
7 3 1 9 5 8 6 2 4
13
5 4 8 2 6 1 3 9 7
14
6 5 4 3 7 2 9 8 1
15
2 8 7 1 9 6 4 3 5
16
1 9 3 5 8 4 7 6 2
17
3 7 5 8 2 9 1 4 6
18
8 6 9 4 1 5 2 7 3
19
4 1 2 6 3 7 8 5 9

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
int m,a,b,sum,flag;
4
char Map[20][20],n; //存放数独
5
void print(){
6
	for(int i=0;i<9;i++){
7
		for(int j=0;j<9;j++){
8
			if(j==0)
9
				printf("%c",Map[i][j]);
10
			else
11
				printf(" %c",Map[i][j]);
12
		}
13
		printf("\n");
14
	}
15
	printf("\n");
16
}
17
bool check(int x,int y,char k){
18
	for(int i=0;i<9;i++){       //横竖直线
19
		if(Map[i][y]==k||Map[x][i]==k)
20
			return false;
21
	}
22
	int x1=x/3*3;		//3*3小矩形 
23
	int y1=y/3*3;
24
	for(int i=x1;i<x1+3;i++){
25
		for(int j=y1;j<y1+3;j++){
26
			if(Map[i][j]==k){
27
				return false;
28
			}
29
		}
30
	}
31
	return true;
32
}
33
void dfs(int x,int y){
34
	if(x==9&&y==0){
35
		flag=1;
36
		print();
37
		return;
38
	}
39
	if(Map[x][y]!='?'){
40
		if(y==8)
41
			dfs(x+1,0);
42
		else
43
			dfs(x,y+1);
44
	}
45
	else{
46
		for(int i=1;i<=9;i++){
47
			if(check(x,y,i+'0')){
48
				Map[x][y]=i+'0';
49
				if(y==8){
50
					dfs(x+1,0);
51
				}
52
				else{
53
					dfs(x,y+1);
54
				}
55
				if(flag==1)
56
					return;
57
				Map[x][y]='?';
58
			}
59
		}
60
	}
61
}
62
int main(){
63
	while(cin>>n){
64
		Map[0][0]=n;
65
		for(int i=0;i<9;i++){
66
			for(int j=0;j<9;j++){
67
				if(i==0&&j==0){
68
					continue;
69
				}
70
				cin>>Map[i][j];
71
			}
72
		}
73
		flag=0;
74
		dfs(0,0);
75
	}
76
	return 0;
77
}