4皇后问题优先队列式分支限界法求解

4皇后问题优先队列式分支限界法求解

算法说明:

1. 使用一个 4x4 的二维数组表示棋盘，0 代表空格，1 代表皇后。
2. 定义一个状态结构体，包含棋盘状态、已放置皇后的行数和当前状态的优先级（代价）。
3. 利用一个优先队列存储状态结构体，按照代价从小到大排序，代价越小的状态越优先被扩展。
4. 初始化状态并加入优先队列。
5. 循环取出优先队列中代价最小的状态，并扩展其子状态。对于每个子状态，计算其代价并加入优先队列。
6. 在扩展子状态时，判断当前行数是否等于 4，如果等于 4，则表示找到一组解，输出该解并结束程序。
7. 如果当前行数小于 4，则在当前行的每个位置都尝试放置皇后，并判断是否合法（同一行、同一列、同一对角线上没有其他皇后）。若合法则生成新的状态，加入优先队列。
8. 计算当前状态的代价，代价为已放置的皇后数量，代价越小的状态优先级越高。
9. 程序循环直到找到一组解或队列为空。

实验程序:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int N = 4; // 棋盘大小

// 状态结构体
struct State {
    int chessboard[N][N]; // 棋盘状态
    int row; // 已经放置的皇后数
    int cost; // 代价
    State(int r = 0, int c = 0) : row(r), cost(c) {
        memset(chessboard, 0, sizeof(chessboard));
    }
};

// 求解4皇后问题
void solve() {
    priority_queue<State, vector<State>, function<bool(State, State)>> q([](State a, State b) {
        return a.cost > b.cost;
    }); // 优先队列，按照代价从小到大排序
    State init;
    q.push(init); // 初始化状态
    while (!q.empty()) {
        State cur = q.top();
        q.pop();
        if (cur.row == N) { // 找到一组解
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    cout << cur.chessboard[i][j] << ' ';
                }
                cout << endl;
            }
            return;
        }
        for (int i = 0; i < N; i++) {
            bool flag = true;
            for (int j = 0; j < cur.row; j++) {
                if (cur.chessboard[j][i] || (i - cur.row + j >= 0 && cur.chessboard[j][i - cur.row + j]) || (i + cur.row - j < N && cur.chessboard[j][i + cur.row - j])) {
                    flag = false; // 当前位置不合法
                    break;
                }
            }
            if (flag) { // 当前位置合法，生成新状态
                State next(cur.row + 1, cur.row);
                memcpy(next.chessboard, cur.chessboard, sizeof(cur.chessboard));
                next.chessboard[cur.row][i] = 1;
                next.cost = next.row;
                q.push(next); // 加入优先队列
            }
        }
    }
}

int main() {
    solve(); // 求解4皇后问题
    return 0;
}

输出结果:

0 1 0 0 
0 0 0 1 
1 0 0 0 
0 0 1 0 

可以看到，程序找到了一组4皇后问题的解。求解过程中，优先队列存储了不同状态，按照代价从小到大排序，每次取出代价最小的状态进行扩展，直到找到一组解或队列为空。