public class Eight_queens{
	static int count=0;
    static Queen q=new Queen();
 public static void main (String[] args) {
    SetQueen(0);
 }
 static void SetQueen(int i){
     for(int j=0;j<=7;j++){
		if(q.isSafe(i,j)){//確定對角線和該列無皇后即可放置在該位置
			q.set(i,j);
			if(i<7) SetQueen(i+1);//遞歸調用setqueen
			else {
			        count++;
					System.out.println("Solution NO."+count+":");
					q.display();//將該情形顯示出來
					System.out.println();
			}
            q.take(i,j);
		}
	}
 }
}

class Queen{
  boolean [][]queen=new boolean[8][8];
  boolean []diag1=new boolean[15];//用于判斷主對角線是否有皇后的矩陣
  boolean []diag2=new boolean[15];//用于判斷次對角線是否有皇后的矩陣
  boolean []col=new boolean[8];//用于判斷同一列是否有皇后的矩陣
  Queen(){ //構造函數，初始化棋盤矩陣和各判定矩陣。
    for(int i=0;i<15;i++){
      for(int j=0;j<8;j++){
      	if(i<8)
          queen[i][j]=true;
      }
      diag1[i]=diag2[i]=true;
      if(i<8) col[i]=true;
    }
  }
   public boolean isSafe(int i,int j){
  	if(diag1[i-j+7]&&diag2[i+j]&&col[j])
  		return true;
  	else
  		return false;
  }
  void set(int i,int j){
    queen[i][j]=false;
    diag1[i-j+7]=diag2[i+j]=col[j]=false;
  }
  void take(int i,int j){
    queen[i][j]=true;
    diag1[i-j+7]=diag2[i+j]=col[j]=true;
  }
  void display(){
	for(int i=0;i<=7;i++){
	   System.out.print("( ");
	   for(int j=0;j<=7;j++)
		   if(queen[i][j]) System.out.print("Q  ");
		   else System.out.print("*  ");
	    System.out.print(")");
	    System.out.println();
	}
}
}