皇后问题(递归)
时间: 1ms 内存:128M
描述:
编写一个函数,求解皇后问题:在n*n的方格棋盘上,放置n个皇后,要求每个皇后不同行、不同列、不同左右对角线。
要求:
1、皇后的个数由用户输入,其值不能超过20,输出所有的解。
2、采用递归回溯的方法解决。
输入:
输入一个整数n,代表棋盘的大小n*n,
输出:
将计算出的彼此不受攻击的n个皇后的所有放置方案输出,每种方案占一行。
示例输入:
4
示例输出:
2 4 1 3
3 1 4 2
提示:
参考答案(内存最优[0]):
#include<iostream>
#include<cmath>
using namespace std;
int q[20]={0};
int place(int k,int j) //测试(k,j)位置能否摆放皇后
{ int i=1;
while (i<k) //i=1~k-1是已放置了皇后的行
{ if ((q[i]==j) || (abs(q[i]-j)==abs(k-i)))
return 0;
i++;
}
return 1;
}
void print(int n)
{
int i;
for(i=1;i<n;i++)
cout<<q[i]<<" ";
cout<<q[i]<<endl;
}
void queen(int k,int n)
{ int j;
if (k>n)
print(n); //所有皇后放置结束输出一组解
else
for (j=1;j<=n;j++) //在第k行上穷举每一个位置
if (place(k,j)) //在第k行上找到一个合适位置(k,j)
{ q[k]=j;
queen(k+1,n);
}
}
int main()
{
int n;
cin>>n;
queen(1,n);
return 0;
}
参考答案(时间最优[0]):
#include<iostream>
#include<cmath>
using namespace std;
int q[20]={0};
int place(int k,int j) //测试(k,j)位置能否摆放皇后
{ int i=1;
while (i<k) //i=1~k-1是已放置了皇后的行
{ if ((q[i]==j) || (abs(q[i]-j)==abs(k-i)))
return 0;
i++;
}
return 1;
}
void print(int n)
{
int i;
for(i=1;i<n;i++)
cout<<q[i]<<" ";
cout<<q[i]<<endl;
}
void queen(int k,int n)
{ int j;
if (k>n)
print(n); //所有皇后放置结束输出一组解
else
for (j=1;j<=n;j++) //在第k行上穷举每一个位置
if (place(k,j)) //在第k行上找到一个合适位置(k,j)
{ q[k]=j;
queen(k+1,n);
}
}
int main()
{
int n;
cin>>n;
queen(1,n);
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。