#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 = color[*ip];

color[*ip] = -1 ;

}

return c ;

}

/*检查区域i,对c种颜色的可用性*/

int colorok( int i , int c , int adj[][N] , int color[ ] )

{
int j ;

for ( j = 0 ; j < i ; j++ )

if (adj[i][j] != 0 && color[j] == c)

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(i,k,adj,color) )

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 =select (i,c+1,adj,color) ) == 0 ){

c = back( &i , color) ;

if ( c == 0) return cnt ;

}
else

{
color[i]=c; 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 ) ) ;coloring( adj ) ;

评论