地图着色问题(java实现)

eliry

public class Coloring
{
private int colors;
private boolean [][]map;
private int []x;
private long sum;    //解法种数

public Coloring(boolean map[][],int colors)
{
  this.map=map;
  this.colors=colors;
  x=new int[map[0].length];
}

public long mColoring()
{
  backtrack(1);
  return sum;
}

private void backtrack(int t)
{
  int n=map[0].length;
  if(t>n)
  {
   sum++;
   print(sum);
  }
  else
  {
   for(int i=1;i<=colors;i++)
   {
    x[t-1]=i;
    if(ok(t)) backtrack(t+1);
   }
  }
}

private boolean ok(int k)
{
  for(int j=0;j<k-1;j++)
  {
   if(map[k-1][j]&&(x[j]==x[k-1]))
    return false;
  }
  return true;
}

private void print(long n)
{
  System.out.println("第"+n+"种方案:");
  for(int i=0;i<x.length;i++)
   System.out.println("第"+(i+1)+"个结点的颜色是："+x[i]);
  System.out.println();
}

public static void main(String []args)
{
  boolean [][] map={{false,true,false,true},
           {true,false,true,false},
           {false,true,false,true},
           {true,false,true,false} };
  int colors=3;
  Coloring mc=new Coloring(map,colors);
  System.out.println("共找到了 "+mc.mColoring()+" 种方案！");
}
}