nhuanhou.cpp

n皇后的问题

/*17． 编写程序对八皇后问题进行求解：在8行8列的棋盘上放置8个皇后，
使任一个皇后都不能吃掉其他的7个皇后（注：皇后可吃掉与她处于同行或
同列或同一对角线上的其他棋子），并将结果以某种方式显示出来。
例如，当求出下述的一个解时，可输出如下信息来表示该解（输出了
表示摆放皇后的坐标位置以及"棋盘状态"- 棋盘中有皇后的位置放一
个"Q"字符，其他位置为"+"字符）。
(1,1) (5,2) (8,3) (6,4) (3,5) (7,6) (2,7) (4,8)
 Q + + + + + + +
 + + + + + + Q +
 + + + + Q + + +
 + + + + + + + Q
 + Q + + + + + +
 + + + Q + + + +
 + + + + + Q + +
 + + Q + + + + +
*/

#include<iostream>
#include <iomanip>
#include <stdlib.h>
using namespace std;

char show[9][9];
class Queen
{
    friend int nQueen(int);
private:
	bool Place(int k);        //测试皇后k能否放在x[k]列上
	void Backtrack(int t);
	int n;                    //皇后个数
	int * x;                  //当前解
	long sum;                 //当前已经找到的可行方案数
};

bool Queen::Place (int k)
{
	for ( int j = 1;  j < k;  j++ ) 
       if ( (abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]) ) return false;
	return true;
}

void Queen::Backtrack(int t)
{
	if(t>n)
	{   
		sum++;
		if(sum==1)
		{
			for(t=1;t<=n;t++)
			{
				show[t][x[t]]='Q';
			}
		}

	}
	else
		for(int i=1;i<=n;i++)
		{
			x[t]=i;                         //在t行i列放一个皇后
			if(Place(t))Backtrack(t+1);     //递归回朔
		}
	
}

int nQueen(int n)           //负责类Queen的私有变量的初始化
{
	Queen X;                //初始化X
	X.n=n;
	X.sum=0;
	int *p=new int[n+1];
	for(int i=0;i<=n;i++)
		p[i]=0;
	X.x=p;
	X.Backtrack(1);         //从第一行开始
	delete [] p;
	return X.sum;
}

void main()
{
    cout<<"**************** n皇后问题 ****************"<<endl;
	cout<<"请输入皇后的个数:";
	int n;
    cin>>n;
	cout<<n<<"皇后的解法有 "<<nQueen(n)<<" 种!"<<endl;
	cout<<"其中的一种解法如下:"<<endl;
	for(int x=1;x<=n;x++)
	{
		for(int y=1;y<=n;y++)
		{
			if(show[x][y]=='Q') goto A;
			show[x][y]='+';
A:			cout<<setw(5)<<show[x][y];
		}
		cout<<endl ;
	}
	   cout<<"系统将退出，";
	system("pause");
}