博客打卡-八皇后问题

题目如下：

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

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

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

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

输入格式

正整数 n (n>0)

输出格式

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

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

输入样例1

3

输出样例1

None

输入样例2

4

输出样例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());
        }
    }
}

提交结果如下：

答案正确