/**
 * 利用回溯法求解N皇后問題
 * 2008/12/04
 * @author jok
 * @version 1.0
 * 
 */

package cn.com.csu.algorithm;

public class NQueen {
  
  private int n;//皇后的個數
  private int[] x;//x[i]表示第i個皇后在第i列第x[i]行
  private long sum;//所有的可行解的個數
  
  public long nQueen(int n) {
    this.n=n;
    sum=0;
    x= new int[n+1];
    for(int i=0;i<=n;i++) {
      x[i] =0;
    }
    backtrack();
    return sum;
  }
  
  private void backtrack() {
    int k=1;
    while(k>0) {
      x[k]+=1;//每次下移一行
      while((x[k]<=n) && !(place(k))) {
        x[k]+=1;//若第x[k]行不能放則判斷下一行
      }
      if(x[k]<=n) {
        if(k==n) {
          sum++;//k==n說明所有的皇后都已經排列好，可行解數目加一
          for(int i=1;i<x.length;i++) {
            System.out.println("第"+i+"個皇后在第"+x[i]+"行第"+i+"列");
          }
          System.out.println("---------------------");
        }
        else {
          k++;//若不是第n列，則繼續判斷下一列
          x[k]=0;
        }
      }
      else {
        k--;//x[k]>n則說明第k列無法排進去，則回溯
      }
    }
  }
  
  /*
   * 判斷第k列第x[k]行能否放皇后，返回true則說明能
   */
  private 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;
  }
  
  public static void main(String[] args) {
    NQueen nq = new NQueen();
    int n = 4;
    nq.nQueen(n);
    System.out.println(n+"皇后問題的可行解有"+nq.sum+"個");
    
  }

}