八皇后的两种解法

public class EightQueue {
private int []x=new int[9];
/*
 * 1.在一列寻找合适的位置，这个位置与前面的所有棋子都不在一条线或者斜线上面
 * 2.当寻找到合适的位置的时候后一列寻找位置
 * 3.当寻找到一个列n个位置后还没有找到好的位置，那么得回溯，并接着寻找上一列的下个位置
 * 4.当回溯到位置0的时候结束。
 */
//判断当前位置的棋子与前面几列的棋子是否碰撞
public boolean isMatch(int n){

for(int i=1;i<n;i++){
if(x[i]==x[n]||Math.abs(n-i)==Math.abs(x[n]-x[i]))
return false;
}
return true;


}

//递归解法

public int  cal(int i){
if(i==0) return 0;

x[i]=x[i]+1;
//向下寻找合适位置
while(i<=8&&!isMatch(i)){
x[i]=x[i]+1;
}
  if(x[i]<=8&&i==8){
return cal(i)+1;

} 
//递归到了最后一个地方
//寻找到了合适位置，向下一列寻找位置
  else if(i<8&&x[i]<=8){
return cal(i+1);
}else{
x[i]=0;
return cal(i-1);
}

}


//非递归解法
public int calculate(){
int sum=0;
for(int i=0;i<9;i++){
x[i]=0;
}
int i=1;
while(i>=1){
x[i]=x[i]+1;
//向下寻找合适位置
while(i<=8&&!isMatch(i)){
x[i]=x[i]+1;
}
//递归到了最后一个地方
if(x[i]<=8&&i==8){
sum++;
} //寻找到了合适位置，向下一列寻找位置
else if(i<8&&x[i]<=8){
i++;
}else{
x[i]=0;
i--;

}

}






return sum;
}

public static void main(String[] args) {
 int n= new EightQueue().cal(1);
 System.out.println(n);
}

}