皇后问题(递归)

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。