皇后问题(递归)

皇后问题(递归)

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

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