fac5_5_1.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 167 页，例
//N后问题的非递归迭代回溯解法
// 
   class NQueen2
   { 
     static int n;         //皇后数
     static int []x;       //  当前解
     static long sum ;     //  当前已找到的可行方案数

    public static long nQueen(int nn)
     {
     n=nn;
     sum=0;
     x=new int[n+1];
     for(int i=0;i<=n;i++)x[i]=0;
        backtrack();
        return sum;
     }
   private static boolean place(int k)
    {
   for(int j=1;j<k;j++)
   if((Math.abs(k-j)==Math.abs(x[j]-x[k]))||(x[j]==x[k]))return false;
   return true;
    }
  private static void backtrack()
   {
    x[1]=0;
    int k=1;
    while(k>0){
      x[k]+=1;
      while((x[k]<=n)&&!(place(k))) x[k]+=1;
    if(x[k]<=n)
      if(k==n)
       {
       sum++;
       System.out.println("八皇后问题的一个方案");
         for(int i=1;i<=n;i++)
           System.out.print("("+i+","+x[i]+")");
         System.out.println();
        }
    else{
      k++;
      x[k]=0;
        }
     else k--;
     }
   }
 }
      public class Fac5_5_1{
      public static void main(String args[])
  {
     int n1=8;
     NQueen2 abc=new NQueen2();
      System.out.println("八皇后问题共有 " + abc.nQueen(n1)+"个解决方案");
  }
}