fac5_5.java

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

//本程序取自王晓东编著“算法分析与设计”第 165 页，例
//N后问题的回溯解法
//本程序输入时注意m 数组需增加一个{0,0}元素，最优值初值选bestf=32767
 
   class NQueen1
   { 
     static int n;         //皇后数
     static int []x;       //  当前解
     static long sum ;     //  当前已找到的可行方案数

    public static long nQueen(int nn)
     {
   //   System.out.println(" ");
     n=nn;
     sum=0;
     x=new int[n+1];
     for(int i=0;i<=n;i++)x[i]=0;
   //   System.out.println(" ");
        backtrack(1);
        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(int t)
   {
    if(t>n){
       sum++;
       System.out.println("八皇后问题的一个方案");
         for(int i=1;i<=n;i++)
           System.out.print("("+i+","+x[i]+")");
         System.out.println();
        }
    else
      for(int i=1;i<=n;i++){
       x[t]=i;
       if(place(t))backtrack(t+1);
      }
   }
 }
      public class Fac5_5{
      public static void main(String args[])
  {
     int n1=8;
     NQueen1 abc=new NQueen1();
      System.out.println("八皇后问题共有 " + abc.nQueen(n1)+"个解决方案");
  }
}