【说明】
著名的四色定理指出任何平面区域图均可用4种颜色着色，使相邻区域着不同的颜色。以下C程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。该程序中用1～4分别表示4种颜色。要着色的N个区域用0～-1编号，区域相邻关系用adj[][]矩阵表示，矩阵的i行j列的元素为1，表示区域i与区域了相邻；矩阵的i行j列的元素为0，表示区域i与区域j不相邻。数组color[]用来存储着色结果，color[i]的值为区域i，所着颜色。
【C程序】
#include ＜stdio.h＞
#define N 10
void output(int color[]) /*输出一种着色方案*/
int i ;
for ( i = 0 ; i ＜ N ; i++ )
printf( "%4d" , color[i] ) ;
printf ("\n") ;
int back(int *ip ,int color[] ) /*回溯*/
intc = 4 ;
while ( c == 4 )
if ( *ip ＜= 0 )
return 0 ;
-- (*ip) ;
c = (1) ;
color[*ip] =-1 ;
return c ;
/*检查区域i，对c种颜色的可用性*/
int colorOk(int i , intc , int [] [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[ ] )
int k ;
for(k = c ; k ＜= 4 ; k++ )
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));
