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

博客打卡-八皇后问题

java 2025/8/11 18:35:20

题目如下：

在国际象棋中，皇后是最厉害的棋子，可以横走、直走，还可以斜走。棋手马克斯·贝瑟尔 1848 年提出著名的八皇后问题：即在 8 × 8 的棋盘上摆放八个皇后，使其不能互相攻击 —— 即任意两个皇后都不能处于同一行、同一列或同一条斜线上。例如：

题图.jpg

现在我们把棋盘扩展到 n×n 的棋盘上摆放 n 个皇后，请问该怎么摆？

请编写程序，输入正整数 n (n≤10)，输出全部摆法。

要求：棋盘空白处显示句点“.”，皇后处显示字母“Q”，两个字符之间空一格，两种摆法之间空一行。

输入格式

正整数 n (n>0)

输出格式

若问题有解，则输出全部摆法。若问题无解，则输出 None。

要求：试探的顺序按从上到下逐行进行，其中每一行按从左到右的逐格进行，请参看输出样例2。

输入样例1

输出样例1

None

输入样例2

输出样例2

. Q . .
. . . Q
Q . . .
. . Q .. . Q .
Q . . .
. . . Q
. Q . .

解题思路：

八皇后问题是一个经典的回溯算法问题，目标是在n×n的棋盘上放置n个皇后，使得它们不能互相攻击，即任意两个皇后不能位于同一行、同一列或同一条斜线上。题目要求对于给定的正整数n（n≤10），找出所有可能的摆放方式，并以特定格式输出每种解法或者在无解时输出"None"。

解题思路主要采用回溯法，从棋盘的第一行开始逐行尝试放置皇后。对于每一行中的每一个位置，检查其是否满足不被其他已放置的皇后攻击的条件（不在相同的列以及两条对角线上）。如果当前位置可以放置皇后，则标记相应的列和对角线为“占用”，然后递归进入下一行继续尝试放置；若某次递归返回意味着后续行无法找到合适位置放置皇后，则撤销当前选择（即回溯），并尝试同一行的下一个位置。当成功放置了n个皇后（即到达了最后一行以下）时，记录或直接打印出一种解法。通过这种方式遍历所有可能的布局，找到所有的解法。如果没有找到任何解法，则最后输出"None"。

代码如下：

import java.util.Scanner;public class Main {static int n;static int[] queens;static boolean[] cols;static boolean[] diag1;static boolean[] diag2;static boolean hasSolution = false;static boolean firstSolution = true;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();if (n <= 0 || n > 10) {System.out.println("None");return;}queens = new int[n];cols = new boolean[n];diag1 = new boolean[2 * n - 1];diag2 = new boolean[2 * n - 1];solve(0);if (!hasSolution) {System.out.println("None");}}static void solve(int row) {if (row == n) {printSolution();hasSolution = true;return;}for (int col = 0; col < n; col++) {if (!cols[col] && !diag1[row + col] && !diag2[row - col + n - 1]) {queens[row] = col;cols[col] = true;diag1[row + col] = true;diag2[row - col + n - 1] = true;solve(row + 1);cols[col] = false;diag1[row + col] = false;diag2[row - col + n - 1] = false;}}}static void printSolution() {if (!firstSolution) {System.out.println();}firstSolution = false;for (int i = 0; i < n; i++) {StringBuilder sb = new StringBuilder();for (int j = 0; j < n; j++) {if (queens[i] == j) {sb.append("Q");} else {sb.append(".");}if (j < n - 1) {sb.append(" ");}}System.out.println(sb.toString());}}
}

提交结果如下：