回溯法求解七巧板涂色问题
算法描述
【问题描述】
有如图所示的七巧板，试编写一源程序如下，使用至多四种不同颜色对七巧板进行涂色(每块涂一种颜色)，要求相邻区域的颜色互不相同，打印输出所有可能的涂色方案。
【问题分析】
为了让算法能识别不同区域间的相邻关 系，我们把七巧板上每一个区域看成一个顶点若两个区域相邻，则相应的顶点间用一条边相连，这样该问题就转化为图一个图的搜索问题了。
C语言实现
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
| #include <stdio.h>
int m, pointnum, edgenum, sum = 0;
int Graph[100][100], x[100];
void InPut() {
int pos1, pos2;
printf("请输入点的个数和色数(p m)：");
scanf("%d%d",&pointnum,&m);
printf("请输入边的个数: ");
scanf("%d",&edgenum);
printf("输入边的起始点信息(起点 终点)：\n");
for(int i = 1; i <= edgenum; ++i) {
scanf("%d%d",&pos1,&pos2);
Graph[pos1][pos2] = Graph[pos2][pos1] = 1;
}
}
int IsOk(int i) {
for(int j = 1; j < i; ++j)
if(Graph[i][j] == 1 && x[j] == x[i])
return 0;
return 1;
}
void BackTrack(int i) {
if(i > pointnum) {
sum += 1;
printf("方法 %d:",sum);
for(int j = 1; j <= pointnum; ++j) {
printf(" %d",x[j]);
}
printf("\n");
} else {
for(int j = 1; j <= m; ++j) {
x[i] = j;
if(IsOk(i))
BackTrack(i + 1);
x[i] = 0;
}
}
}
int main() {
InPut();
BackTrack(1);
printf("一共有%d种绘色方案",sum);
}
|
运行截图
