本系列博客源自学习《尚硅谷数据结构与算法》的学习随笔。
八皇后问题介绍:
思路分析:
代码:
package test.learn.algorithm.recursion;
public class Queue8 {
//定义max表示皇后的数量
int max = 8;
//定义一个数组,保存皇后最终存放的位置
int [] array = new int[max];
int count = 0;
public static void main(String[] args) {
Queue8 queue8 = new Queue8();
queue8.check(0);
System.out.println("一共有"+ queue8.count+"种解法");
}
//将皇后摆放的位置输出
private void print(){
count++;
for(int i = 0 ; i < array.length ; i++){
System.out.print(array[i]+" ");
}
System.out.println();
}
//判断是否冲突
private boolean judge(int n){
for(int i = 0 ; i < n ; i++){
//array[i]==array[n] 表示两个皇后不同位于同一列
//Math.abs(n-i)==Math.abs(array[n]-array[i]) 表示两个皇后不能位于同一斜线 y = |x|
//不可能放在同一行
if(array[i]==array[n]||Math.abs(n-i)==Math.abs(array[n]-array[i])){
return false;
}
}
return true;
}
//编写方法放置皇后
private void check(int n){
if(n==max){
print();
return;
}
//按列放入皇后
for(int i = 0 ; i < max ; i++){
array[n] = i;
//判断是否冲突
if(judge(n)){//不冲突
check(n+1);
}
//如果冲突就继续执行遍历
}
}
}
结果(截取部分):