n皇后问题的求解答案-CSDN下载

下载 > 课程资源 > C/C++ > n皇后问题的求解答案

: n皇后问题的求解答案

2011-07-06 上传大小：28KB N皇后

#include <iostream>
#include <vector>
using namespace std;

void backtrack(int, vector<int>, int, int);
bool place(int, vector<int>);
void displayqueen(vector<int>, int, int);

int sum = 0;

int main(void)
{
	int N;
	int kind;
	
	cout<<"请输入皇后的个数：";
	cin>>N;
	vector<int> x(N+1,0);
	
	cout<<"----------------------------------"<<endl;
	cout<<'\t'<<"结果显示的形式："<<endl;
	cout<<'\t'<<"  1.直接形式."<<endl;

                            cout<<'\t'<<"  2.矩阵形式."<<endl;
	cout<<"----------------------------------"<<endl;
	cout<<"请输入你想显示结果的形式：";
	cin>>kind;
	
	backtrack(1, x, N, kind);
	
	return 0;
}

void backtrack(int t, vector<int> x, int N, int kind)
{
	if(t > N)
	{
		sum += 1;
		displayqueen(x, N, kind);
	}
	else
	{
		for(int i=1; i<N+1; i++)
		{
			x[t] = i;
			
			if(place(t, x))
			{
				backtrack(t+1, x, N, kind);
			}
		}
	}
}

bool place(int k, vector<int> x)
{
	for(int j=1; j<k; j++)
	{
		if((abs(k-j) == abs(x[k]-x[j])) || (x[k] == x[j]))
		{
			return false;
			break;
		}
	}
	
	return true;
}

void displayqueen(vector<int> x, int N, int kind)
{
	if(kind == 1)
	{
		cout<<"第"<<sum<<"个解：";
		
		for(int i=1; i<N+1; i++)
		{
			cout<<x[i]<<' ';
		}
		cout<<endl;
	}
	else
	{
		vector<vector<int> > S(N+1, vector<int>(N+1));

		for(int i=1; i<N+1; i++)
		{
			for(int j=1; j<N+1; j++)
			{
				S[i][j] = 0;
			}
		}

		for(i=1; i<N+1; i++)
		{
			for(int j=1; j<N+1; j++)
			{
				S[i][x[i]] = 1;
			}
		}
		
		cout<<"第"<<sum<<"个解："<<endl;
		
		for(i=1; i<N+1; i++)
		{
			for(int j=1; j<N+1; j++)
			{
				cout<<S[i][j]<<' ';
			}
			cout<<endl;
		}
	}
}

...展开收缩

综合评分：5

收藏评论(1)举报

所需: 3积分/C币下载个数： 5