问题概述
设计一个解n后问题的队列式分支限界法，计算在方格上放置彼此不受攻击的n个皇后的一个放置方案。
Code
#include<bits/stdc++.h>
using namespace std;
#define N 100
int n;
struct node{
int vis[N]={0}, col[N]={0}, lr[N]={0}, rl[N]={0};
int x, y;
node(int a, int b):x(a), y(b){}
bool operator<(const node& a)const{
return x<a.x;
}
};
priority_queue<node>q;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
node temp=node(0, i);
temp.vis[0]=i+1;
temp.col[i]=1;
temp.rl[temp.x+temp.y]=1;
temp.lr[50+temp.x-temp.y]=1;
q.push(temp);
}
while(!q.empty()){
node temp=();
q.pop();
if(temp.x==n-1){
for(int i=0;i<n;i++)
{
cout<<temp.vis[i]<<" ";
}
cout<<endl;
break;//只输出一个答案
}
if(temp.x<n-1){
for(int i=0;i<n;i++)
{
node t=node(temp.x+1, i);
if(temp.col[t.y]||temp.lr[50+t.x-t.y]||temp.rl[t.x+t.y]){//剪枝
continue;
}
for(int i=0;i<N;i++){
t.lr[i]=temp.lr[i];
t.rl[i]=temp.rl[i];
t.col[i]=temp.col[i];
}
t.col[t.y]=1;
t.lr[50+t.x-t.y]=1;
t.rl[t.x+t.y]=1;
for(int i=0;i<t.x;i++){
t.vis[i]=temp.vis[i];
}
t.vis[t.x]=i+1;
q.push(t);
}
}
}
return 0;
}
