皇后问题（栈和队列）
时间： 1ms 内存：128M
描述：
编写一个函数，求解皇后问题：在n*n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。
要求：
1、皇后的个数由用户输入，其值不能超过20，输出所有的解。
2、采用类似于栈求解迷宫问题的方法。
输入：
输入一个整数n，代表棋盘的大小n*n，
输出：
将计算出的彼此不受攻击的n个皇后的所有放置方案输出，每种方案占一行。
示例输入：
4
示例输出：
2 4 1 3
3 1 4 2提示：
参考答案（内存最优[0]）：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Max_Size 20
int q[Max_Size+1];
bool place(int q[],int k)
{
int i;
for(i=1;i<k;i++)//注意此处不能小于等于，若小于等于则没有结果
{
if(q[i]==q[k] || (fabs(k-i) == fabs(q[k]-q[i])))
return false;
}
return true;
}
void print_solution(int q[],int n)
{
/*int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(j == q[i])
printf("Q ");
else
printf("* ");
}
printf("\n");
}
printf("\n");*/
int i;
for(i=1;i<=n;i++)
{
if(i!=n)
printf("%d ",q[i]);
else
printf("%d\n",q[i]);
}
}
void nQueen(int q[],int n)
{
int k=1;
q[k] = 0;
while(k>0)
{
q[k]++;
while(q[k]<=n && !place(q,k))
q[k]++;
if(q[k]<=n)
{
if(k==n)
print_solution(q,n);
else
{
k++;
q[k] = 0;
}
}
else
k--;
}
}
int main()
{
int n;
//printf("请输入是几皇后：");
scanf("%d",&n);
if(n > Max_Size)
{
// printf("数字过大！\n");
exit(0);
}
nQueen(q,n);
return 0;
}
参考答案（时间最优[0]）：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Max_Size 20
int q[Max_Size+1];
bool place(int q[],int k)
{
int i;
for(i=1;i<k;i++)//注意此处不能小于等于，若小于等于则没有结果
{
if(q[i]==q[k] || (fabs(k-i) == fabs(q[k]-q[i])))
return false;
}
return true;
}
void print_solution(int q[],int n)
{
/*int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(j == q[i])
printf("Q ");
else
printf("* ");
}
printf("\n");
}
printf("\n");*/
int i;
for(i=1;i<=n;i++)
{
if(i!=n)
printf("%d ",q[i]);
else
printf("%d\n",q[i]);
}
}
void nQueen(int q[],int n)
{
int k=1;
q[k] = 0;
while(k>0)
{
q[k]++;
while(q[k]<=n && !place(q,k))
q[k]++;
if(q[k]<=n)
{
if(k==n)
print_solution(q,n);
else
{
k++;
q[k] = 0;
}
}
else
k--;
}
}
int main()
{
int n;
//printf("请输入是几皇后：");
scanf("%d",&n);
if(n > Max_Size)
{
// printf("数字过大！\n");
exit(0);
}
nQueen(q,n);
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。