/******************************問題描述：******************************   
    
  設在初始狀態下在國際象棋棋盤上沒有任何棋子(皇后)。然后順序在第一行，第   
  2行，...第8行上布放棋子。在每一行中有8個可選位置，但在任一時刻，棋盤的   
  合法布局都必須滿足3個限制條件，即任何兩個棋子不得放在棋盤的同一行、同一   
  列、或者同一斜線上。   
    
  ***********************************************************************/  


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.*;


public class Queen8 
{

	/**
	 * @param args
	 */
	static int count = 0; 					//解法的個數
	
	
	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		System.out.println("Please input the number of the queens ");
	
		try
		{
			String str;
			BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
			str = in.readLine();
			int n = Integer.parseInt(str);
			if(n < 4)
			{
				System.out.println("Sorry!There are so few queens that it isn't worth to do it!");
			}
			else if(n > 200)
			{
				System.out.println("Sorry!There are too many queens that I can't solve it!");
			}
			else
			{
				int QueenMax;
				QueenMax = n;
				int chess[] = new int[QueenMax];
				for(int i = 0; i < QueenMax; i++)
				{
					chess[i] = -1;
				}
				placequeen(0, QueenMax, chess); 
				System.out.println("\nThere are " + count + 
						" solutions for the problem " + 
						QueenMax + "_Queens in total"); 
			}
		}
		catch(IOException e)
		{
			
		}

	}
	
	public static void placequeen(int num, int QueenNum, int chess[])      //num 為現在要放置的行數
	{  
		int i=0; 
		boolean queenSave[] = new boolean[QueenNum]; 
		for(; i < QueenNum; i++) 
			queenSave[i] = true; 

		//下面先把安全位數組完成 
		i=0;//i 是現在要檢查的數組值 
		while (i < num)
		{ 
			queenSave[chess[i]] = false; 
		    int k = num-i; 
		    if ( (chess[i]+k >= 0) && (chess[i]+k < QueenNum) ) 
		    	queenSave[chess[i]+k]=false; 
		    if ( (chess[i]-k >= 0) && (chess[i]-k < QueenNum) ) 
		    	queenSave[chess[i]-k]=false; 
		    i++; 
		}
		//下面歷遍安全位 
		for(i=0; i<QueenNum; i++)
		{ 
		   if (queenSave[i] == false)
			   continue; 
		   if (num < QueenNum-1)
		   { 
			   chess[num] = i; 
			   placequeen(num+1, QueenNum, chess); 
		   }
		   else
		   { //num is last one 
			   chess[num] = i; 
			   count ++; 
			   System.out.println("");
			   System.out.println("Solution NO." + count + ":"); 
			   for (i=0; i < QueenNum; i++)
			   { 
				   String row="";
				   if (chess[i]==0); 
				   else 
					   for(int j=0;j < chess[i];j++) 
						   row+="* "; 
				   row+="Q "; 
				   int j = chess[i]; 
				   while(j < QueenNum - 1)
				   {
					   row += "* ";
					   j++;
				   } 
				   System.out.println(row); 
			   }
		   	}
		}
		//歷遍完成就停止 
	}

}