【说明】
著名的四色定理指出任何平面区域均可以用4种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。
【函数】
# include ＜stdio.h＞
#define N 10 /*要着色的N个区域*/
void output(int color[]) /*输出一种着色方案 color[i]的值为区域i所着颜色*/
int i;
for (i=0; i＜N; i++)
printf("%4d", color[i]);
printf("\n");
int back(int *ip, int color[j] /*回溯*/
int c=4;
while (c==4)
if (*ip＜=0)
return 0:
--(*ip);
c= (1) ;
color[*ip]=-1;
return c;
/*检查区域i，考查c种颜色的可能性 */
int colorOK(iht i, int c, int adj[][N], int color[])
int j;
for(j=0; j＜i; j++)
if ( (2) )
return 0;
return 1;
/*为区域i选一种可着的颜色*/
int select(int i, int c, int adj[][N], int color[])
/*寻找各种着色方案 adj[i][j]=1表示区域i与区域j不相邻*/
int k;
for (k=c; k＜=4; k++) /*4种颜色*/
if (colorOK( (3) ))
return k;
return 0;
int coloring(int adj[][N])
int color[N], i, c, cnt;
for (i=0; i＜N; i++) color[i]=-1:
i=c=0; cnt=0;
while (1)
[
if ((c= (4) )==0)
c=back(&i, color);
if (c==0)
return cnt;
else
(5) ;
i++;
if(i==N)
output(color);
++cnt;
c=back(&i, color);
else
c=0;
void main()
int adj[N][N]= 0, 1, 0, 1, 1, 1, 1, 1, 1, 1,
1, 0, 1, 1, 0, 1, 1, 1, 1, 0,
0, 1, 0, 1, 0, 1, 1, 0, 1, 1,
1, 1, 1, 0, 1, 1, 0, 0, 1, 1,
1, 0, 0, 1, 0, 1, 0, 0, 0, 0,
1, 1, 1, 1, 1, 0, 1, 0, 0, 1,
1, 1, 1, 0, 0, 1, 0, 0, 1, 0,
1, 1, 0, 0, 0, 0, 0, 0, 1, 1,
1, 1, 1, 1, 0, 0, 1, 1, 0, 1,
1, 0, 1, 1, 0, 1, 0, 1, 1, 0
;
printf("共有%d 组解.\n", coloring(adj));
