//本程序取自王曉東編著“算法分析與設(shè)計”第 167 頁，例
//N后問題的非遞歸迭代回溯解法
// 
   class NQueen2
   { 
     static int n;         //皇后數(shù)
     static int []x;       //  當(dāng)前解
     static long sum ;     //  當(dāng)前已找到的可行方案數(shù)

    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)+"個解決方案");
  }
}