编写一个实验程序采用优先队列式分支限界法求解4皇后问题的一个解 将一个4x4的棋盘用二维数组表示

#include #include #include using namespace std;

const int N = 4; int queen[N]; // 存放每行皇后的列号

struct Node { int row; int col; int threat; // 剩余威胁数 Node(int r=0, int c=0, int t=0): row(r), col(c), threat(t) {} bool operator < (const Node& b) const { return threat > b.threat; // 剩余威胁数越小，优先级越高 } };

int calcThreat(int row, int col) { int cnt = 0; for (int i = 0; i < row; i++) { // 检查前面的每一行 if (queen[i] == col) cnt++; // 同列 if (queen[i]+i == col+row) cnt++; // 同一主对角线 if (queen[i]-i == col-row) cnt++; // 同一副对角线 } return cnt; }

bool solve() { priority_queue q; // 优先队列 for (int i = 0; i < N; i++) { q.push(Node(0, i, calcThreat(0, i))); // 第一行的节点进队列 } while (!q.empty()) { Node node = q.top(); q.pop(); queen[node.row] = node.col; // 记录当前行的皇后位置 if (node.row == N-1) return true; // 已找到一个解 // 产生下一行的节点 for (int i = 0; i < N; i++) { int threat = calcThreat(node.row+1, i); if (threat == 0) { // 无威胁，直接进队列 q.push(Node(node.row+1, i, 0)); } else { // 有威胁，计算下一行可能的最小威胁数 int minThreat = N; for (int j = 0; j < N; j++) { if (j != i) { int t = calcThreat(node.row+2, j); if (t < minThreat) { minThreat = t; } } } q.push(Node(node.row+1, i, minThreat)); } } } return false; // 无解 }

int main() { if (solve()) { cout << "Solution:" << endl; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (j == queen[i]) { cout << "Q "; } else { cout << ". "; } } cout << endl; } } else { cout << "No solution." << endl; } return 0;