N皇后问题:
问题表述为:在N×N格的国际象棋上摆放N个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
实现思路为暴力遍历递归,在每次递归前去判断是否满足条件,不满足条件即立即进行剪枝操作
话不多说,直接上 bug
。
package test;
import java.util.Scanner;
public class QueenTest {
public static int[] queens;
public static int num = 0;
public static boolean check(int row){
for(int i = 0;i < row;i++){
if(queens[row] == queens[i] || Math.abs(queens[row] - queens[i]) == Math.abs(row-i)){
return false;
}
}
return true;
}
public static void print(int temp[]) {
for (int i = 0; i < temp.length; i++) {
for (int j = 0; j < temp[i]; j++) {
System.out.print("☆" + "\t");
}
System.out.print("★" + "\t");
for (int j = temp.length - 1; j > temp[i]; j--) {
System.out.print("☆" + "\t");
}
System.out.println();
}
}
public static void queen(int row,int n){
if(row == n){
num++;
System.out.println("-----------------------------------第"+ num +"种解:-----------------------------------");
print(queens);
}else {
for(int i = 0;i < n;i++){
queens[row] = i;
if(check(row)){
queen(row + 1,n);
}
}
}
}
public static void main(String[] args) {
System.out.println("请输入需要的阶数:");
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
queens = new int[n];
queen(0,n);
scan.close();
}
}
注:其中当皇后阶数即n大于12时,程序运行时间则会进行陡增。
改进点:all