经典算法八皇后问题有多少种解法？你想知道吗...
最新推荐文章于 2022-12-16 14:33:34 发布
原创
最新推荐文章于 2022-12-16 14:33:34 发布
·
1w 阅读
·
5
·
8
·
CC 4.0 BY-SA版权
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
文章标签：
#算法
#java
本文介绍了一种解决经典八皇后问题的算法实现。通过递归和冲突检测，演示了如何在8x8的棋盘上放置8个皇后，使得任意两个皇后都不在同一行、同一列或同一对角线上。代码使用Java语言编写，详细展示了布局过程和所有可能的解决方案。
摘要生成于
C知道
，由 DeepSeek-R1 满血版支持，
前往体验 >
运行结果
说明
在本题中，棋盘是由8行8列，共64个格子构成
运行结果中的 [7, 3, 0, 2, 5, 1, 6, 4] 的意思是：
第1行第8(7+1)列放第1个皇后第2行第4(3+1)列放第2个皇后第3行第1(0+1)列放第3个皇后其它依此类推…
示意图如下：
12345678********源代码
import java.util.Arrays;
// 八皇后问题求解
public class Queue8 {
// 皇后的个数
int max = 8;
// 摆放方案的个数
static int count = 0;
// 保存每个皇后的位置，因为每行只放一个皇后，所以只用了一个一维数组保存列号即可
int[] arr = new int[max];
public static void main(String[] args) {
Queue8 queue8 = new Queue8();
queue8.layout(0);
System.out.println("八皇后问题共有"+count+"个解法");
}
// 放置皇后
private void layout(int n) {
if(n == max) {
// 这时说明已经摆放完了
System.out.println(Arrays.toString(arr));
count++;
return;
}
// 对每个皇后，都依次去尝试摆放在每一列
for(int i = 0; i < max; i++) {
arr[n] = i;
// 判断这个皇后摆放位置是否冲突
if(judge(n)) {
// 如果当前位置不冲突，继续递归，摆放下一个皇后
layout(n+1);
}
// 如果发生冲突，进入下一轮循环，尝试摆放在下一列
}
}
// 判断第n个皇后是否和前面的冲突
private boolean judge(int n) {
for(int i = 0; i < n; i++) {
// 判断是否在同一列，或一条对角线上
if(arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[i] - arr[n])) {
return false;
}
}
return true;
}
}