4 皇后问题优先队列分支限界法求解 - Java 代码实现 - 常规

4 皇后问题优先队列分支限界法求解 - Java 代码实现

4 皇后问题是一个经典的计算机科学问题，要求在一个 4x4 的棋盘上放置 4 个皇后，使得任何两个皇后都不在同一行、同一列或同一对角线上。

本文将介绍使用优先队列分支限界法求解 4 皇后问题的解决方案，并提供完整的 Java 代码实现。

算法步骤

初始化优先队列： 将初始状态（棋盘全为 0，表示空位）加入队列。
取出优先级最高状态： 每次从队列中取出优先级最高的状态，即已放置皇后数量最少的那个状态。
尝试放置皇后： 对于当前状态，依次尝试在每一列放置皇后，生成新的状态并加入队列中。
检查规则： 对于新生成的状态，检查是否符合规则，即同行、同列、同对角线无重复皇后。如果新状态不符合规则，则舍弃该状态。
输出解： 如果新状态已经放置了 4 个皇后，则输出解并结束程序。
无解： 如果队列为空，则表示无解。

代码实现

import java.util.PriorityQueue;

public class NQueens {
    static class State implements Comparable<State> {
        int[][] board; // 棋盘状态
        int queens; // 已放置皇后数量
        int priority; // 优先级，即已放置皇后数量

        public State(int[][] board, int queens) {
            this.board = board;
            this.queens = queens;
            this.priority = queens;
        }

        @Override
        public int compareTo(State o) { // 优先级比较器
            return Integer.compare(this.priority, o.priority);
        }
    }

    public static void main(String[] args) {
        int[][] board = new int[4][4]; // 初始状态，棋盘全为 0
        PriorityQueue<State> queue = new PriorityQueue<>(); // 优先队列
        queue.offer(new State(board, 0)); // 将初始状态加入队列

        while (!queue.isEmpty()) {
            State state = queue.poll(); // 取出优先级最高的状态
            if (state.queens == 4) { // 如果已经放置了 4 个皇后，则输出解并结束程序
                printBoard(state.board);
                return;
            }
            for (int col = 0; col < 4; col++) { // 在每一列尝试放置皇后
                if (isValid(state.board, state.queens, col)) { // 检查是否符合规则
                    int[][] newBoard = copyBoard(state.board); // 生成新状态
                    newBoard[state.queens][col] = 1; // 放置皇后
                    queue.offer(new State(newBoard, state.queens + 1)); // 加入队列
                }
            }
        }
        System.out.println("No solution found.");
    }

    private static boolean isValid(int[][] board, int row, int col) {
        // 检查同列
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 1) {
                return false;
            }
        }
        // 检查左上对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }
        // 检查右上对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < 4; i--, j++) {
            if (board[i][j] == 1) {
                return false;
            }
        }
        return true;
    }

    private static int[][] copyBoard(int[][] board) {
        int[][] newBoard = new int[4][4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                newBoard[i][j] = board[i][j];
            }
        }
        return newBoard;
    }

    private static void printBoard(int[][] board) {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
}

代码解释

State 类： 该类用于表示棋盘状态，包含棋盘数组 board、已放置皇后数量 queens 和优先级 priority。优先级等于已放置皇后数量，用于优先队列排序。
main 方法： 程序入口，初始化棋盘和优先队列，并开始循环处理队列中的状态。
isValid 方法： 检查新生成状态是否符合规则，即同行、同列、同对角线无重复皇后。
copyBoard 方法： 复制棋盘数组，用于生成新的状态。
printBoard 方法： 打印棋盘状态。

总结

本文介绍了使用优先队列分支限界法解决 4 皇后问题，并提供了完整的 Java 代码实现。该方法通过优先队列管理状态，并使用剪枝策略提高效率，可以有效地找到 4 皇后问题的解。

该代码示例仅供参考，可以根据实际需求进行调整和扩展。例如，可以将代码扩展到解决更一般的 N 皇后问题。