四色定律.c

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[])
{
	int c=4;
	while(c==4)
	{
		if(*ip<=0) return 0;
		--(*ip);
		c=color[*ip];
		color[*ip]=-1;
	}
	return 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 0;
}

int select(int i,int c,int adj[][N],int color[])
{
	int k;
	for (k=c;k<=4;k++)
	{
		if(colorOK(i,c,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]=-i;
	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
		{
			   ;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,0,1,1,0},
		{1,0,1,1,0,1,1,1,1,0},
		{1,1,1,1,0,0,1,1,0,1},
		{1,1,0,0,0,0,0,0,1,1},
		{0,1,0,1,0,1,1,0,1,1},
		{1,1,1,0,1,1,0,0,1,1},
		{1,1,1,0,0,1,0,0,1,0},
		{1,0,0,1,0,1,0,0,0,0},
		{1,1,1,1,1,0,1,0,0,1}
		
			
	};
	printf("共有%d组解.\n",coloring(adj));
}