/**
* 八皇后——>n皇后
* 描述:在8X8棋盘放8个皇后,任何一个皇后都无法直接吃掉其他的皇后,问一共有多少种方法
* 时间:2018-7-21 16:47:11
* @author LousenJay
*
*/
public class Queen {
private int num = 8; //设置皇后的个数
public static int count = 0; //计数
private int[] array = new int[num]; //保存结果,第一个皇后在array[0],第二个在array[1]
/**
* 打印结果
*/
private void print(int n){
//打印一组结果
System.out.println("第"+n+"组:");
for (int i = 0; i < num; i++) {
System.out.print(array[i]+1+" ");
}
System.out.println();//换行
System.out.println("棋盘展示:");
for (int i = 0; i < num; i++) { //打印行
for (int j = 0; j < num; j++) { //打印列
if(j == array[i]){
System.out.print("♛");
}else{
System.out.print("☒");
}
}
System.out.println();
}
System.out.println();
}
/**
* 判断第n行的皇后在当前列和对角线上是否有皇后
* 如果有则返回false,循环下一个列继续匹配
* 如果该列符合则返回true,开始下一行查找
* @param n
* @return
*/
private boolean judge(int n){
for (int i = 0; i < n; i++) {
//判断第n行的皇后在当前列和对角线上是否有皇后
if(array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])){
return false;
}
}
return true;
}
/**
* n代表当前放的是第几个皇后
* array[n]代表第n个皇后的列的位置
* @param n
*/
private void find(int n){
/*如果皇后全部放完了,则计数并打印该种方法*/
if(n == num){
count++;//计数
print(count);//输出
return;
}
/*开始第一组查找,先从第一行的8个列开始查找,符合条件开始依次查找第二行,
* 八行全部符合条件,查找结束,计数+1并打印结果
* 不符合就开始查找第二组
* 最后所有结果全部查找完毕,跳出递归循环*/
for (int i = 0; i < num; i++) {
array[n] = i; //遍历每一列放置的八种可能,列
if(judge(n)){ //行
find(n+1); //递归查找第二列
}
}
}
public static void main(String[] args) {
Queen q = new Queen();
q.find(0); //从第一行开始查找
System.out.println("总计:"+q.count+"种方法");
}
}