#include <iostream>
#include <math.h>
using namespace std;
int queen; //皇后數目
int *pos; //放置的位置

//判斷第n行是否放置皇后
bool SignPoint(int n)
{
	for (int i=0;i<n;i++)
	{
		if (*(pos+i) == *(pos+n)) //該列已經放置過皇后了
			return false;
		if (abs(*(pos+i) - *(pos+n)) == n-i) //對角線已經放置過了
			return false;
	}
	return true;
}
//設置皇后
void SetQueens(int n=0)
{
	if (queen==n)
	{
		for (int i=0;i<queen;i++)
		{
			for (int j=0;j<queen;j++)
			{
				if (j == pos[i])
					cout<<" * ";
				else
					cout<<" 0 ";
			}
			cout<<endl;
		}
		cout<<endl;
		return;
	}
	else
	{	
		for (int i=0;i<queen;i++)
		{
			pos[n] = i;
			if(SignPoint(n))//如果該位置放置皇后正確的話,則到下一行
			SetQueens(n+1);
		}
	}
}

int main()
{
	system("color 0F");  //設置當前窗口的背景色和前景色,數字中前一位為背景,后一位為前景
						 // 0 = 黑色   8 = 灰色
						 // 1 = 藍色   9 = 淡藍色 
						 // 2 = 綠色   A = 淡綠色 
					 	 // 3 = 淺綠色 B = 淡淺綠色 
						 // 4 = 紅色   C = 淡紅色 
						 // 5 = 紫色   D = 淡紫色 
						 // 6 = 黃色   E = 淡黃色 
						 // 7 = 白色   F = 亮白色
	cout<<"請輸入皇后的總數:"<<endl;
	cin>>queen;
	pos = new int[queen];
	SetQueens();
	cout<<"皇后擺放完畢!"<<endl;
	return 0;
}