//////////////////////////////////////////////////////
//采用回溯法求解n皇后問題
//用函數進行回溯
//
//經過適當的優化后可以算到32
//
//完成于2007.7.15
//
///////////////////////////////////////////////////////
#include <iostream>

#include <vector>

#include <algorithm>

#include <math.h>
#include <windows.h>
using namespace std;

typedef vector<int> stack;

int backnum = 0;

void PrintMatrix(int **matrix,int n)
{
	int i = 0,j = 0;
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			if(matrix[i][j] == 1)
			{
				cout<<"*"<<' ';
			}
			else if(matrix[i][j] == 0)
			{
				cout<<"#"<<' ';
			}
			else
			{
				cout<<'a'<<' ';
			}
		}
		cout<<endl;
	}

}

bool CheckMatrix(int **matrix,int i,int j,int n)
{
	int able = 0;
	int lie = 0;
	matrix[i][j] = 1;
	//做合法性檢查
	//不在同一列
	for(lie = i; lie >= 0; lie--)
	{
		if(matrix[lie][j] == 1)
		{
			able++;
		}
	}
	//不在正對角線上
	int num = 0;
	if(i > j)
	{
		num = j;
	}
	else
	{
		num = i;
	}

	for(lie = 0;lie <= num; lie++)
	{
		if(matrix[i-lie][j-lie] == 1)
		{
			able++;
		}
	}
	//不在反對角線上
	if(i > n-1-j)
	{
		num = n-1-j;
	}
	else
	{
		num = i;
	}
	for(lie = 0;lie <= num; lie++)
	{
		if(matrix[i-lie][j+lie] == 1)
		{
			able++;
		}
	}
	if(able == 3)
	{
		return true;
	}
	else
	{
		matrix[i][j] = 0;
		return false;
	}

}

int ChangeMatrix(int **matrix,int i,int j,int n,int value)
{
	int able = 0;
	int lie = 0;
	int origin = matrix[i][j];
	//做合法性檢查
	//同一列
	int Change = 0;
	for(lie = i; lie < n; lie++)
	{
		if(matrix[lie][j] != value)
		{
			matrix[lie][j] = value;
			Change++;
		}
	}
	//正對角線上
	int num = 0;
	if(i > j)
	{
		num = n-1-i;
	}
	else
	{
		num = n-1-j;
	}

	for(lie = 0;lie <= num; lie++)
	{
		if(matrix[i+lie][j+lie] != value)
		{
			matrix[i+lie][j+lie] = value;
			Change++;
		}
		
	}
	//反對角線上
	if(j > n-1-i)
	{
		num = n-1-i;
	}
	else
	{
		num = j;
	}
	for(lie = 0;lie <= num; lie++)
	{
		if(matrix[i+lie][j-lie] != value)
		{
			matrix[i+lie][j-lie] = value;
			Change++;
		}
	
	}
	
	matrix[i][j] = origin;
	return Change;
}

void ChangeMatrix(int **matrix,int n)
{
	int i = 0,j = 0;
	for(i = 0;i < n; i++)
	{
		for(j = 0;j < n; j++)
		{
			if(matrix[i][j] == 2)
			{
				matrix[i][j] = 0;
			}
		}
	}
	for(i = 0;i < n; i++)
	{
		for(j = 0;j < n; j++)
		{
			if(matrix[i][j] == 1)
			{
				ChangeMatrix(matrix,i,j,n,2);
			}
		}
	}

}



void Queen(int **matrix,int i,int j,int n)
{
	backnum++;
	int able = 0;
	int lie = 0,hang = 0;
	int pos = 0;
	if(i == 0 && j == 0)
	{
		matrix[i][j] = 1;
		//ChangeMatrix(matrix,n);
		ChangeMatrix(matrix,i,j,n,2);
		Queen(matrix,i+1,2,n);//下一行
		return;
	}
	else if(j > n -1) //一行找到頭了，回退
	{
		/*
		cout<<"i = "<<i<<endl;
		cout<<"j = "<<j<<endl;
		cout<<"backnum = "<<backnum<<endl;
		PrintMatrix(matrix,n);
		//*/
		///*
		
		int num = 0;
		for(lie = 0; lie < n; lie++)
		{
			if(matrix[i-1][lie] == 1)
			{
				matrix[i-1][lie] = 0;
				pos = lie;
			//	break;
			}
		}
		/*
		for(lie = 0; lie < n; lie++)
		{
			num += matrix[i][lie];
		}
		if(num == 2*(n-1))
		{
			cin>>lie;
			Queen(matrix,i,0,n);ChangeMatrix(matrix,n);//不回退從這一行的起始位置開始
			return;
		}
		//*/
		//*/
		//ChangeMatrix(matrix,i-1,pos,n,0);
		//matrix[i-1][pos] = 0;
		ChangeMatrix(matrix,n);
		
	
		Queen(matrix,i-1,pos+1,n);//從上一行的下一個位置開始
		return;
	}
	else if(i == n-1 && j > n -1)
	{
		cout<<"無解------"<<endl;
		return;
	}
	else 
	{
		if(matrix[i][j] == 0 &&CheckMatrix(matrix,i,j,n))//可以放做下一行
		//if(CheckMatrix(matrix,i,j,n))
		{
			//ChangeMatrix(matrix,i,j,n,2);
			ChangeMatrix(matrix,n);
			/*
			cout<<"i = "<<i<<endl;
			cout<<"j = "<<j<<endl;
			cout<<"backnum = "<<backnum<<endl;
			PrintMatrix(matrix,n);
			//*/
			if(i == n-1)
			{
				cout<<"找到解了--------"<<endl;
				PrintMatrix(matrix,n);
				return;
			}
			else
			{
				for(lie = 0;lie < n; lie++)
				{
					if(matrix[i+1][lie]==0)
						break;
				}
				Queen(matrix,i+1,lie,n);
				/*
				
				if(j+2 < n&& i < n)
				{

					if(j+2>lie)
					{
					Queen(matrix,i+1,j+2,n);
					}
					else
					{
						Queen(matrix,i+1,lie,n);
					}
				}
				else
				//*/
				{
					//Queen(matrix,i+1,0,n);
				}
				return;
			}
		}
		else//不可以做,做這一行的下一個元素
		{
			Queen(matrix,i,j+1,n);
			
			return;
		}
		
	}

}

int first = 0;
int next = 0;
int Select(int **matrix,int i,int n)
{
	int lie = 0;
	int num = n;
	int CM = 0;
	//找出改變次數最少的那個值
	for(int j = 0;j < n; j++)
	{
		if(matrix[i][j]==0)
		{
			CM = ChangeMatrix(matrix,i,j,n,2);
			if(num > CM)
			{
				num = CM;
				lie = j;
			}
			ChangeMatrix(matrix,n);
		}
	}
	return lie;
}
void Queen1(int **matrix,int i,int j,int n)
{
	backnum++;
	int able = 0;
	int lie = 0,hang = 0;
	int pos = 0;
	if(i == 0 && j == 0)
	{
		matrix[i][j] = 1;
		//ChangeMatrix(matrix,n);
		ChangeMatrix(matrix,i,j,n,2);
		Queen1(matrix,i+1,2,n);//下一行
		return;
	}
	else if(j > n -1) //一行找到頭了，回退
	{
		/*
		cout<<"i = "<<i<<endl;
		cout<<"j = "<<j<<endl;
		cout<<"backnum = "<<backnum<<endl;
		PrintMatrix(matrix,n);
		//*/
		///*
		
		int num = 0;
		for(lie = 0; lie < n; lie++)
		{
			if(matrix[i-1][lie] == 1)
			{
				matrix[i-1][lie] = 0;
				pos = lie;
			//	break;
			}
		}
		/*
		for(lie = 0; lie < n; lie++)
		{
			num += matrix[i][lie];
		}
		if(num == 2*(n-1))
		{
			cin>>lie;
			Queen(matrix,i,0,n);ChangeMatrix(matrix,n);//不回退從這一行的起始位置開始
			return;
		}
		//*/
		//*/
		//ChangeMatrix(matrix,i-1,pos,n,0);
		//matrix[i-1][pos] = 0;
		ChangeMatrix(matrix,n);
		
	
		Queen1(matrix,i-1,pos+1,n);//從上一行的下一個位置開始
		return;
	}
	else if(i == n-1 && j > n -1)
	{
		cout<<"無解------"<<endl;
		return;
	}
	else 
	{
		if(matrix[i][j] == 0 &&CheckMatrix(matrix,i,j,n))//可以放做下一行
		//if(CheckMatrix(matrix,i,j,n))
		{
			//ChangeMatrix(matrix,i,j,n,2);
			ChangeMatrix(matrix,n);
			/*
			cin>>first;
			cout<<"i = "<<i<<endl;
			cout<<"j = "<<j<<endl;
			cout<<"backnum = "<<backnum<<endl;
			PrintMatrix(matrix,n);
			//*/
			if(i == n-1)
			{
				cout<<"找到解了--------"<<endl;
				PrintMatrix(matrix,n);
				return;
			}
			else
			{
				int sum = 0;
				for(hang = i+1; hang < n; hang++)
				{
					sum = 0;
					for(lie = 0; lie < n; lie++)
					{
						sum+=matrix[hang][lie];
					}
					if(n*2 == sum)
					{
						for(lie = j+1;lie < n; lie++)
						{
							if(matrix[i][lie]==0)
							break;
						}
						matrix[i][j] = 0;
						ChangeMatrix(matrix,n);
						Queen1(matrix,i,lie,n);
						return;
					}
				}
				//////////////////////////////////
				//可以算到32
				///*
				if(i < n/2-1)
				{
				//*	
				if(j == 0)
					{
						Queen1(matrix,i+1,j,n);
					}
					else if(j+2 < n)
					{
						Queen1(matrix,i+1,j+2,n);
					}
					else
					{
						//Queen1(matrix,i+1,0,n);
						Queen1(matrix,i+1,(j+2)%n,n);
						//Queen1(matrix,i+1,(j+2)%(n-1),n);
					}
					//*/
					return;
				}
				else
				{
					lie = Select(matrix,i+1,n);
					Queen1(matrix,i+1,lie,n);
					return;
				}
				return;
			}
		}
		else//不可以做,做這一行的下一個元素
		{
			for(lie = j+1;lie < n; lie++)
				{
					if(matrix[i][lie]==0)
						break;
				}
			Queen1(matrix,i,lie,n);
			
			return;
		}
		
	}

}

void main()

{
	cout<<"八皇后問題:"<<endl;
	int n = 0;
	do
	{
	cout << "請輸入皇后的個數：" ;
	cin >> n;
	int **matrix;
	matrix = new int*[n];
	int i = 0 , j = 0;
	for(i = 0; i < n; i++)
	{
		matrix[i] = new int[n];
		for(j = 0; j < n; j++)
		{
			matrix[i][j] = 0;
		}
		
	}
	//PrintMatrix(matrix,n);
	//*
	first = n/2;
	next = n/2;
	if(n%2 == 0)
	{
		Queen1(matrix,0,n/2,n);
	}
	else
	{
		Queen1(matrix,0,n/2,n);
	}
	//*/
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			if(matrix[i][j] == 1)
			{
				cout<<j<<' ';
			}
		}
	}
	cout<<endl;
	cout<<"backnum = "<<backnum<<endl;
	backnum = 0;
	}while(n >= 4);
	
}