/**
 * @(#)Queens.java
 *
 *
 * @author 
 * @version 1.00 2008/3/31
 */


public class Queens {

    
     int size;
    int resultCount=0;
    
    public void compute ( int size ) {
        this.size = size;
        
        int data[] = new int[size];
        int count; // 所有可能的情況個數
        int i,j;
        
        // 計算所有可能的情況的個數
        count = 1;
        for ( i=0 ; i<size ; i++ ) {
            count = count * size;
        }
        // 對每一個可能的情況
        for ( i=0 ; i<count ; i++ ) {
            // 計算這種情況下的棋盤上皇后的擺放位置，用 8 進制數表示
            // 此處可優化
            int temp = i;
            for ( j=0 ; j<size ; j++ ) {
                data [j] = temp % size;
                temp = temp / size;
            }
            // 測試這種情況是否可行，如果可以，輸出
            if ( test(data) )
                output( data );
        }
    }

    /*
     * 測試這種情況皇后的排列是否可行
     * 
     */
    public boolean test( int[] data ) {
        int i,j;
        for ( i=0 ; i<size ; i++ ) {
            for ( j=i+1 ; j<size ; j++ ) {
                // 測試是否在同一排
                if ( data[i] == data[j] )
                    return false;
                // 測試是否在一斜線
                if ( (data[i]+i) == (data[j]+j) )
                    return false;
                // 測試是否在一反斜線
                if ( (data[i]-i) == (data[j]-j) )
                    return false;
            }
        }
        return true;
    }

    /*
     * 輸出某種情況下皇后的坐標
     *
     */
    public void output ( int[] data ) {
        int i;
        resultCount++;
        System.out.println("Solution No. "+resultCount );
        for (i=0; i<size; i++)
        {
        	if (data[i]==0) System.out.println("Q * * * * * * *");
        	else if (data[i]==1 ) System.out.println("* Q * * * * * *");
        	else if (data[i]==2 ) System.out.println("* * Q * * * * *");
        	else if (data[i]==3 ) System.out.println("* * * Q * * * *");
        	else if (data[i]==4 ) System.out.println("* * * * Q * * *");
        	else if (data[i]==5 ) System.out.println("* * * * * Q * *");
        	else if (data[i]==6 ) System.out.println("* * * * * * Q *");
        	else if (data[i]==7 ) System.out.println("* * * * * * * Q");
        }
        System.out.println();
        
    }
    public static void main(String args[]) {
        (new Queens()).compute( 8 );
    }

    
}