//構造原理
/*
一、當n mod 6 != 2 且 n mod 6 != 3時，有一個解為：
2,4,6,8,...,n,1,3,5,7,...,n-1       (n為偶數)
2,4,6,8,...,n-1,1,3,5,7,...,n       (n為奇數)

(上面序列第i個數為ai，表示在第i行ai列放一個皇后；... 省略的序列中，相鄰兩數以2遞增。下同)

二、當n mod 6 == 2 或 n mod 6 == 3時，
(當n為偶數,k=n/2；當n為奇數,k=(n-1)/2)

k,k+2,k+4,...,n,2,4,...,k-2,k+3,k+5,...,n-1,1,3,5,...,k+1         (k為偶數,n為偶數)
k,k+2,k+4,...,n-1,2,4,...,k-2,k+3,k+5,...,n-2,1,3,5,...,k+1,n       (k為偶數,n為奇數)

k,k+2,k+4,...,n-1,1,3,5,...,k-2,k+3,...,n,2,4,...,k+1               (k為奇數,n為偶數)
k,k+2,k+4,...,n-2,1,3,5,...,k-2,k+3,...,n-1,2,4,...,k+1,n           (k為奇數,n為奇數)

*/

#include <iostream>
#include <vector>
using namespace std;

void NQueen(int *Queen,int n)
{
	int mod = n%6;
	int div = n%2;
	int i = 0,j = 0,k = 0;
	
	if(mod != 2 && mod != 3)
	{
		if( div == 0)
		{
			for(i = 0,j = 2; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if( j == n)
				{
					j = 1-2;
				}
			}

		}
		else
		{
			for(i = 0,j = 2; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if( j == n-1)
				{
					j = 1-2;
				}
			}
		}
	}
	else//當n mod 6 == 2 或 n mod 6 == 3時
	{
		if(div == 0)//n為偶數
		{
			k = n/2;
		}
		else        //n為奇數
		{
			k = (n-1)/2;
		}
		int kk = k%2;
		//k,k+2,k+4,...,n,2,4,...,k-2,k+3,k+5,...,n-1,1,3,5,...,k+1(k為偶數,n為偶數)
		if(div == 0 && kk == 0)
		{
			for(i = 0,j = k; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if(j == n)
				{
					j = 2-2;
				}
				else if(j == k-2)
				{
					j = k+3-2;
				}
				else if(j == n-1)
				{
					j = 1-2;
				}

			}
		}
		//k,k+2,k+4,...,n-1,2,4,...,k-2,k+3,k+5,...,n-2,1,3,5,...,k+1,n(k為偶數,n為奇數)
		if(kk == 0 && div != 0)
		{
			for(i = 0,j = k; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if(j == n-1)
				{
					j = 2-2;
				}
				else if(j == k-2)
				{
					j = k+3-2;
				}
				else if(j == n-2)
				{
					j = 1-2;
				}
				else if(j == k+1)
				{
					j = n - 2;
				}
					 
			}

		}
		//k,k+2,k+4,...,n-1,1,3,5,...,k-2,k+3,...,n,2,4,...,k+1(k為奇數,n為偶數)
		if(kk != 0 && div == 0)
		{
			for(i = 0,j = k; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if(j == n-1)
				{
					j = 1-2;
				}
				else if(j == k-2)
				{
					j = k+3-2;
				}
				else if(j == n)
				{
					j = 2-2;
				}
			}
		}
		//k,k+2,k+4,...,n-2,1,3,5,...,k-2,k+3,...,n-1,2,4,...,k+1,n(k為奇數,n為奇數)
		if(kk == 1 && div == 1)
		{
			for(i = 0,j = k; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if(j == n-2)
				{
					j = 1-2;
				}
				else if(j == k-2)
				{
					j = k+3-2;
				}
				else if(j == n-1)
				{
					j = 2-2;
				}
				else if(j == k+1)
				{
					j = n-2;
				}
			}

		}
	}


}

void Print(int *Queen,int n)
{
	for(int  i = 0; i < n; i++)
	{
		cout<<Queen[i]<<' ';
	}
	cout<<'\n';
}

bool Check(int *Queen,int n)
{
	int i = 0,j = 0;
	int wrong = 0;
	for(i = 0; i < n; i++)
	{
		for(j = i+1; j < n; j++)
		{
			if(Queen[i] == Queen[j] || Queen[i]-i == Queen[j]-j || Queen[i]+i == Queen[j]+j )
			{
				wrong++;
			}
		}
	}
	cout<<"wrong="<<wrong<<endl;
	if(wrong == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
void main()
{
	int n = 0;
	int *Queen;
	do
	{
	cout<<"請輸入皇后的個數：";
	cin>>n;
	Queen =  new int[n];
	for(int i = 0; i < n; i++)
	{
		Queen[i] = 0;
		cout<<"i = "<<i <<endl;
	}
	cout<<"i = "<<i <<endl;
	NQueen(Queen,n);
	Check(Queen,n);
	Print(Queen,n);
	delete Queen;
	}while(n > 4);

}