首页 > 代码库 > 8皇后问题

8皇后问题

2024-07-16 13:31:59   218人阅读

题目：在8×8的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。请求出总共有多少种摆法。
思路：一般是通过递归、回溯来求得，这里有一种新的方式，那就是通过全排列。
由于八个皇后的任意两个不能处在同一行，那么这肯定是每一个皇后占据一行。于是我们可以定义一个数组ColumnIndex[8]，数组中第i个数字表示位于第i行的皇后的列号。先把ColumnIndex的八个数字分别用0-7初始化，接下来我们要做的事情就是对数组ColumnIndex做全排列。由于我们是用不同的数字初始化数组中的数字，因此任意两个皇后肯定不同列。我们只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上，也就是数组的两个下标i和j，是不是i-j==ColumnIndex[i]-Column[j]或者j-i==ColumnIndex[i]-ColumnIndex[j]。
 思路来自：http://zhedahht.blog.163.com/blog/static/2541117420114331616329/

代码：

/*
八皇后
by Rowandjj
2014/8/8
*/
#include<iostream>
using namespace std;
int num = 0;//种数
void permutation(int arr[],int len,int index)
{
	if(index == len - 1)
	{
		bool flag = true;
		for(int i = 0; i < len; i++)
		{
			for(int j = i+1; j < len; j++)
			{
				if(i-j==arr[i]-arr[j] || i-j==arr[j]-arr[i])//在对角线上
				{
					flag = false;			
					break;
				}
			}
		}		
		if(flag)
		{
			num++;
			for(int i = 0; i < len; i++)
			{
				cout<<arr[i]<<" ";
			}
			cout<<endl;
		}
	}else
	{
		for(int i = index;i < len; i++)
		{
			int temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
			
			permutation(arr,len,index+1);
			
			temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
		}
	}
}
void eightQueenSolution()
{
	int len = 8;
	int arr[] = {0,1,2,3,4,5,6,7};
	permutation(arr,len,0);
}
int main()
{
	eightQueenSolution();
	cout<<num<<endl;
	return 0;
}



联系
我们