和用栈求解迷宫问题思路相似,特此记录下。
代码:
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 100
int n,num=1;//num定义为全局变量
typedef struct node {
int col[maxn];//col[i]表示第i个n皇后的列数,(i,col[i])即为坐标
int top;
}stacktype;
void display(stacktype st)
{
printf(" 第%d个解为:",num++);
for(int i=1;i<=n;i++)
printf("(%d,%d) ",i,st.col[i]);
printf("\n");
}
bool place(stacktype st,int k,int j)
{
int i=1;
if(k==1) return true;//第一个皇后直接放入,没有任何冲突
while(i<=k-1)//遍历前k-1个皇后,判断第k个皇后是否可以放在(k,j)处
{
if((st.col[i]==j)||(abs(st.col[i]-j)==abs(i-k)))
return false;
i++;
}
return true;
}
void queen(int n)
{
int k;
bool find;
stacktype st;
st.top=1;
st.col[st.top]=0;
while(st.top!=0)
{
k=st.top;//记录栈顶皇后的个数
find=false;
for(int j=st.col[k]+1;j<=n;j++)//回溯时要遍历当前列后面的列数,且下一个皇后的初始化列数为0
if(place(st,k,j))
{
st.col[k]=j;
find=true;
break;//找到第一个可以放入的位置
}
if(find)
{
if(k==n)
{
display(st);//每次能放完n个皇后都要输出
}
else
{
st.top++;
st.col[st.top]=0;
}
}
else st.top--;//回溯,最后while结束时是当第一个皇后放在(1,n)位置时无法将n个皇后都放下,st.top=0
}
if(num==1)
printf(" 此%d皇后问题无解!\n",n);
}
int main()
{
printf("n皇后问题求解:n=");
scanf("%d",&n);
if(n>20) printf("n必须小于20\n");
else
{
printf(" %d皇后问题的求解情况如下:\n",n);
queen(n);
}
return 0;
}