package nqueens;
public class NQueen {
private final int size; // 棋盘的大小,也表示皇后的数目
private int[] location; // 皇后在棋盘的每行上的列的位置
private boolean[] colsOccupied; // 皇后在棋盘上占据的列
private boolean[] cross1Occupied; // 皇后在棋盘上占据的正对角线
private boolean[] cross2Occupied; // 皇后在棋盘上占据的反对角线
private static int count; // 解决方案的个数
public NQueen(int size) {
this.size = size;
location = new int[size];
colsOccupied = new boolean[size];
cross1Occupied = new boolean[2 * size];
cross2Occupied = new boolean[2 * size];
}
private void printLocation() {
System.out.println("以下是皇后在棋盘上的第" + count + "种摆放位置");
for (int i = 0; i < size; i++)
System.out.println("行:" + i + "列:" + location[i]);
}
// 判断位置(i,j)是否被占领
private boolean isOccupied(int i, int j) {
return colsOccupied[j] || (cross1Occupied[i - j + size - 1]) || (cross2Occupied[i + j]);
}
// 如果参数flag为1,表示占领位置(i,j);
// 如果参数flag为0,表示取消占领位置(i,j);
private void setStatus(int i, int j, boolean flag) {
colsOccupied[j] = flag; // 宣布占领或取消占领第j列;
cross1Occupied[i - j + size - 1] = flag; // 宣布占领或取消占领正对角线
cross2Occupied[i + j] = flag; // 宣布占领或取消占领反对角线
}
// 从第i行开始摆放皇后
public void place(int i) {
for (int j = 0; j < size; j++)
// 在第i行分别尝试把皇后放在每一列上
if (!isOccupied(i, j)) // 判断该位置是否被占领
{
location[i] = j; // 摆放皇后,在第i行把皇后放在你j列
setStatus(i, j, true); // 宣布占领(i,j)位置
if (i < size - 1)
place(i + 1); // 如果所有皇后没有摆完,递归摆放下一行皇后
else {
count++; // 统计解决方案的个数
printLocation(); // 完成任务,打印所有皇后的位置
}
// 回溯,取消占领位置(i,j)
setStatus(i, j, false);
}
}
public void start() {
place(0); // 从第0行开始放置皇后
}
public static void main(String[] args) {
// TODO Auto-generated method stub
new NQueen(4).start(); // 开始执行n皇后
}
}
![avatar](https://profile-avatar.csdnimg.cn/823be93c18be4b9fa55c75bb75c369e0_weixin_42659791.jpg!1)
Kinonoyomeo
- 粉丝: 80
- 资源: 1万+
最新资源
- 打包和分发Rust工具.pdf
- SQL中的CREATE LOGFILE GROUP 语句.pdf
- C语言-leetcode题解之第172题阶乘后的零.zip
- C语言-leetcode题解之第171题Excel列表序号.zip
- C语言-leetcode题解之第169题多数元素.zip
- ocr-图像识别资源ocr-图像识别资源
- 图像识别:基于Resnet50 + VGG16模型融合的人体细胞癌症分类模型实现-图像识别资源
- C语言-leetcode题解之第168题Excel列表名称.zip
- C语言-leetcode题解之第167题两数之和II-输入有序数组.zip
- C语言-leetcode题解之第166题分数到小数.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback-tip](https://img-home.csdnimg.cn/images/20220527035111.png)
评论0