#include <iostream.h>
#include <math.h>
#include <time.h>

const int N=8;
int X[N+1];

bool place(int k)
{//如果一個皇后能放在第k行和X(k)列，則返回true,否則返回false。
	//X是一個全程數組，進入此過程時已設置了k個值。
	int i=1;
	while(i<k)
	{
		if(X[i]==X[k] || abs(X[i]-X[k])==abs(i-k))
			return false;
		i=i+1;
	}
	return true;
}

void n_queens(int n)
{
	int k;
	k=1;//k是當前行
    X[1]=0;//X[k]是當前行
    int j=0;//記錄解的個數
    cout<<"所有可能的解如下："<<endl;
	while(k>0)
	{  
		X[k]=X[k]+1;
		while(X[k]<=n && !place(k))
		{
			X[k]=X[k]+1;
		}
		if(X[k]<=n)
			if(k==n)
			{ 
				cout<<"第"<<++j<<"組解:";
				for(int i=1; i<=n; i++)
					cout<<X[i]<<"   ";
				cout<<endl;
			}
			else
			{
				k=k+1;
				X[k]=0;
			}
			else
				k=k-1;
	}
}

int main()
{
    clock_t start, finish; 
	double duration; 
	/* 測量此事件持續的時間*/ 
	time_t t;
	time(&t);
	start = clock();
	
	n_queens(N);
	
    time(&t); 
	
	finish = clock(); 
	duration = (double)(finish - start) / CLOCKS_PER_SEC; 
	cout<<endl;
	cout<<"用時"<<duration<<"秒"<<endl;
	return 1;
}