八皇後問題是個很經典的遞歸、迭代問題。解決思路就是只要保證所有皇後不在同一列和同斜線上。
假設就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個
