搜索技术【深度优先搜索】 - DFS+ 剪枝优化 【POJ No. 2676】数独游戏 Sudoku

搜索技术【深度优先搜索】 - DFS+ 剪枝优化 【POJ No. 2676】数独游戏 Sudoku

在深度优先搜索过程中，如果没有剪枝，就属于暴力穷举，往往会超时。剪枝函数包括约束函数（能否得到可行解的约束）和限界函数（能否得到最优解的约束）。有了剪枝函数，就可以剪掉得不到可行解或最优解的分支，避免无效搜索，提高搜索效率。在深度优先搜索算法中，剪枝优化是关键。剪枝函数设计得好，会大大提高搜索效率。

POJ 题目地址

【题意】

数独是一项非常简单的任务。如下图所示，

一张9行9列的表被分成9个3×3的小方格。在一些单元格中写上十进制数字1～9，其他单元格为空。目标是用1～9的数字填充空单元格，每个单元格一个数字，这样在每行、每列和每个被标记为3×3的子正方形内，所有1～9的数字都会出现。编写一个程序来解决给定的数独任务。

【输入输出】

输入：

输入数据将从测试用例的数量开始。对于每个测试用例，后面都跟9行，对应表的行。在每一行上都给出9个十进制数字，对应这一行中的单元格。如果单元格为空，则用0表示。

输出：

对于每个测试用例，程序都应该以与输入数据相同的格式打印解决方案。空单元格必须按照规则填充。如果解决方案不是唯一的，那么程序可以打印其中任何一个。

【样例】

【思路分析】

本题为数独游戏，为典型的九宫格问题，可以采用回溯法搜索。把一个9行9列的网格再细分为9个3×3的子网格，要求在每行、每列、每个子网格内都只能使用一次1～9的一个数字，即在每行、每列、每个子网格内都不允许出现相同的数字。

0表示空白位置，其他均为已填入的数字。要求填完九宫格并输出（如果有多种结果，则只需输出其中一种）。如果给定的九宫格无法按要求填出来，则输出原来所输入的未填的九宫格。

用3个数组标记每行、每列、每个子网格已用的数字。

• row[i ][x ]：用于标记第i 行中的数字x 是否出现。
• col[j ][y ]：用于标记第j 列中的数字y 是否出现。
• grid[k ][z ]：标记第k 个3×3子网格中的数字z 是否出现。

row和col的标记比较好处理，关键是找出grid子网格的序号与行i、 列j 的关系，即要知道第i 行j 列的数字属于哪个子网格。

把一个9行9列的网格再细分为9个3×3的子网格，在每个子网格内都不允许出现相同的数字，那么我们将9个子网格编号为1～9，在同一个子网格内不允许出现相同的数字。

观察子网格的序号k 与行i、 列j的关系：

• 如果把第1～3行转换为0，第4～5行转换为1，第7～9行转换为2，则a =(i -1)/3；
• 如果把第1～3列转换为0，第4～5列转换为1，第7～9列转换为2，则b =(j -1)/3。

行i、 列j 对应的子网格编号k =3×a +b +1=3×((i -1)/3)+(j-1)/3+1，如下图所示。

【算法设计】

① 预处理输入数据。

② 从左上角(1,1)开始按行搜索，如果行i =10，则说明找到答案，返回1。

③ 如果map[i ][j ]已填数字，则判断如果列j =9，则说明处理到当前行的最后一列，继续下一行第1列的搜索，即dfs(i +1,1)，否则在当前行的下一列搜索，即dfs(i , j +1)。如果搜索成功，则返回1，否则返回0。

④ 如果map[i ][j ]未填数字，则计算当前位置(i ,j )所属子网格k =3×((i -1)/3)+(j -1)/3+1。枚举数字1～9填空，如果当前行、当前列、当前子网格均未填该数字，则填写该数字并标记该数字已出现。如果判断列j =9，则说明处理到当前行的最后一列，继续下一行第1列的搜索，即dfs(i +1,1)，否则在当前行的下一列搜索，即dfs(i, j +1)。如果搜索失败，则回溯归位，继续搜索，否则返回1。

【算法实现】

#include
#include

using namespace std;

int map[10][10];

bool row[10][10]; //row[i][x] 标记在第i 行中数字x 是否已经出现
bool col[10][10]; //col[j][y] 标记在第j 列中数字y 是否已经出现
bool grid[10][10]; //grid[k][z] 标记在第k 个3*3 的子格中数字z 是否已经出现

bool dfs(int i, int j){
	
	if(i == 10){
		
		return 1;
	}
	bool flag = 0;
	if(map[i][j]){
		
		if(j == 9){
			
			flag = dfs(i + 1, 1);
		}
		else{
			flag = dfs(i , j + 1);
		}
		return flag ? 1 : 0;
	}
	else{
		
		int k = 3 * ((i - 1) / 3) + (j - 1) / 3 + 1;
		for(int x = 1; x <= 9 ; x++){ //枚举数字1~ 9 填空 
			
			if(!row[i][x] && !col[j][x] && !grid[k][x]){
				
				map[i][j] = x;
				row[i][x] = 1;
				col[j][x] = 1;
				grid[k][x] = 1;
				
				if(j == 9){
					
					flag = dfs(i + 1 , 1);
				}
				else{
					flag = dfs(i , j + 1);
				}
				if(!flag) { //回溯，继续枚举 
					
					map[i][j] = 0;
					row[i][x] = 0;
					col[j][x] = 0;
					grid[k][x] = 0;
				}
				else{
					return 1;
				}
			}
		}
	}
	return 0;
} 

void init(){
	
	memset(row , false, sizeof(row));
	memset(col , false, sizeof(col));
	memset(grid , false , sizeof(grid));
	
	char ch;
	for(int i = 1; i <= 9; i ++){
		
		for(int j = 1; j <= 9; j ++){
			
			cin >> ch;
			map[i][j] = ch - '0';
			if(map[i][j]){
				
				int k = 3 * ((i - 1) / 3) + (j - 1) / 3 + 1;
				row[i][map[i][j]] = 1;
				col[j][map[i][j]] = 1;
				grid[k][map[i][j]] = 1;
			}
		}
	}
}

int main(){
	
	int T;
	cin >> T;
	
	while(T --){
		
		init();
		dfs(1 ,1);
		
		for(int i = 1; i <= 9 ; i++){
			
			for(int j = 1; j <= 9 ; j ++){
				
				cout << map[i][j];
			}
			cout << endl;
		}
	}
	
	return 0;
}





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
106
107
108
109
110
111
112
113
114
115