nqueen.java

包括冒泡排序

/**
 * 利用回溯法求解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+"个");
    
  }

}