package com.ykh.huisu;
/*递归回溯解决八皇后问题
* */
public class Queen8 {
int[] array=new int[8];//用数组表示每个皇后的位置
int count=0;//记录排列的方法的总数
//判断第n个皇后和前面n-1个皇后是否在同一列或者同一斜线上
public boolean isOk(int n) {
for(int i=0;i<n;i++) {
if(array[i]==array[n]||Math.abs(array[n]-array[i])==Math.abs(n-i)) {
return false;
}
}
return true;
}
//摆放皇后的方法，将会用到递归回溯
/*基本方法是：
* 1）先将第一个皇后放在第一行第一列 array[0]=0;
* 2）在将第二个皇后放在第二行，从第二行第一列开始，逐渐向右移，直到皇后不冲突
* 3）以后的每一个皇后都按照这样的方法在每一行进行摆放
* 4）若找不到一个位置能满足条件，就回溯，上一个皇后的位置就应该发生改变
* 5)只要找到了一个满足条件的解，也要回溯，上一个皇后的位置发生改变，然后找下一个位置,
* */
public void putQueen(int n) {
if(n==8) {//n=8时所有的皇后都摆好了，这个时候只需要将数组打印出来就可以了
print();
count++;
return;
}
for(int i=0;i<8;i++) {
array[n]=i;
if(isOk(n)) {
putQueen(n+1);
}
}
}
//打印皇后位置的数组
public void print() {
int len=array.length;
for(int i=0;i<len;i++) {
System.out.print(array[i]+"");
}
System.out.println();
}
public static void main(String[] args) {
Queen8 test=new Queen8();
test.putQueen(0);
System.out.println(test.count);
}
