当前位置：首页 > news >正文

【JAVA】第1关：非递归实现皇后问题

news 2024/11/5 2:48:28

任务描述
编程要求
测试说明
任务描述
本关任务：在n×n格的棋盘上放置彼此不受攻击的 n 个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。用非递归算法解决该问题。

下图是一个 8 个皇后的例子，8 个皇后彼此不受攻击。

在这里插入图片描述

编程要求
请在右侧编辑器Begin-End处补充代码，完成本关任务。

测试说明
平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：

测试输入：4（皇后的数目）

预期输出：

在这里插入图片描述

4皇后问题共有2种摆放方案
开始你的任务吧，祝你成功！

package step1;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;public class Nqueens {private int n; // 棋盘的大小，即N皇后问题的Nprivate Stack<Integer> stack; // 用于存储每一行皇后的列位置private List<int[]> solutions; // 用于存储所有解决方案// 构造函数，初始化N皇后问题的参数public Nqueens(int n) {this.n = n;this.stack = new Stack<>();this.solutions = new ArrayList<>();}// 解决N皇后问题的主方法public void solve() {int row = 0; // 当前处理的行int col = 0; // 当前处理的列// 当栈不为空或当前行小于n时，继续寻找解决方案while (!stack.isEmpty() || row < n) {// 在当前行中寻找合适的列放置皇后while (col < n) {if (isSafe(row, col)) { // 检查当前位置是否安全stack.push(col); // 将当前列位置压入栈中row++; // 进入下一行col = 0; // 重置列，从下一行的第0列开始break; // 跳出内层循环，继续处理下一行}col++; // 尝试下一列}// 如果已经处理完所有行，说明找到了一个解决方案if (row == n) {int[] solution = new int[n]; // 创建一个解决方案数组for (int i = 0; i < n; i++) {solution[i] = stack.get(i); // 将栈中的列位置复制到解决方案数组中}solutions.add(solution); // 将解决方案添加到解决方案列表中row--; // 回溯到上一行col = stack.pop() + 1; // 弹出栈顶元素，并从下一列开始继续寻找} else if (col == n) { // 如果当前行没有找到合适的列if (stack.isEmpty()) { // 如果栈为空，说明已经遍历完所有可能的组合return; // 结束程序}row--; // 回溯到上一行col = stack.pop() + 1; // 弹出栈顶元素，并从下一列开始继续寻找}}}// 检查在(row, col)位置放置皇后是否安全private boolean isSafe(int row, int col) {for (int i = 0; i < row; i++) {int placedCol = stack.get(i); // 获取第i行皇后的列位置if (placedCol == col || // 检查是否在同一列placedCol - i == col - row || // 检查是否在同一主对角线placedCol + i == col + row) { // 检查是否在同一副对角线return false; // 如果存在冲突，返回false}}return true; // 如果没有冲突，返回true}// 打印所有解决方案public void printSolutions() {for (int[] solution : solutions) {for (int i = 0; i < solution.length; i++) {System.out.print("  "); // 打印行前缀空格for (int j = 0; j < solution.length; j++) {if (solution[i] == j) { // 如果当前位置是皇后System.out.print("Q"); // 打印皇后} else {System.out.print("*"); // 否则打印空位}if (j < solution.length - 1) {System.out.print("  "); // 打印列间空格}}System.out.println(); // 换行}System.out.println(); // 打印解决方案之间的空行}System.out.println(n + "皇后问题共有" + solutions.size() + "种摆放方案"); // 打印解决方案总数}// 主函数，程序入口public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 读取用户输入的N值scanner.close();Nqueens nQueens = new Nqueens(n); // 创建N皇后问题的实例nQueens.solve(); // 解决N皇后问题nQueens.printSolutions(); // 打印所有解决方案}
}