#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 ) ;

评论