/*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");
}