#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[ ]）{ /*回溯*/
int c = 4 ;
while （ c == 4 ）{
if （ *ip <= 0 ）
return 0 ;
--（*ip） ;
c = __（1）__ ;
color[*ip] = -1 ;
}
return c ;
}
/*检查区域 i ，对 c 种颜色的可用性*/
int colorOK（int I,int c,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 ） ;
}
e1se 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））;
} |
|