你的位置:首页 > Java教程

[Java教程]八皇后问题


八皇后问题是个很经典的递归、迭代问题。解决思路就是只要保证所有皇后不在同一列和同斜线上。

假设就j,k为两个皇后所在的行 x[j]、x[k]表示两个皇后的位置。当两个皇后在同一列或同斜线上 可以用数学式子来表达|j-k|=|x[j]-x[k]|、x[j]=x[k]。所有当这两个条件不满足的时候问题就能解决。

解决方法一:递归法

private int n; //皇后个数
private int sum; //解的个数
private int x[]; //当前解
public EightQueens(){
  this.n=8;
  this.sum=0;
  this.x=new int [n+1];
}
/**
* 约定i表示行 x[i]表示位置
*/

public void jie(int t){
  if(t>n){/*如果t>n表示搜索到叶子节点 一次深度搜索结束*/
    sum++;
  }else{
    for(int i=1;i<=n;i++){
      x[t]=i;
      if(place(t)){
        jie(t+1);
       }
    }
  }
}
/**
* 判断函数,判断是否在一列上或者在同一条斜线上
* @param k
* @return
*/
public boolean place(int k){
  for(int j=1;j<k;j++){
  if((Math.abs(j-k))==(Math.abs(x[j]-x[k]))||(x[j]==x[k])){
    return false;
  }
}
  return true;
}

 运行结果 :92个

解决方法二:回溯

while(t>=1){
  x[t]=x[t]+1; //在下一列放置第k个皇后
  while(x[t]<=8&&!eightqueens.place(t)){
    x[t]=x[t]+1;//搜索下一列
  if(x[t]<=8&&t==8)//得到一个输出{
    eightqueens.sum++;
  }
  else if(x[t]<=8&&t<8)
    t=t+1;//放置下一个皇后
  else{
    x[t]=0;//重置x[k],回溯
    t=t-1;
  }
}

 运行结果 :92个