//The code bellow is written by Carla Martin alone.

public class nQueens {
    //first dimension is the rows, second the columns.
    public static int[][] board;

    public nQueens( int n )
    {
        board = new int[ n ][ n ];
    }
    
    public static boolean placeQueens() {
        int numQueens = numQueensOnBoard();
        int numOpenSpots = numOpenSpots();

        if( numOpenSpots >= 1 && board.length - numQueens == 1 )
        {
            int row = getOpenSpotRow( 0 );
            int col = getOpenSpotCol( 0 );
            addQueen( row, col );
            return true;
        }
        else if( numOpenSpots == 0 )
            return false;

        for( int i = 0; i < numOpenSpots; ++i ) {
            int row = getOpenSpotRow( i );
            int col = getOpenSpotCol( i );
            addQueen( row, col );
            if( placeQueens() )
                return true;
            else
                removeQueen( row, col );
        }
        return false;
    }

       //Updates the board.
    private static void update( int row, int col, int increment ) {
        int size = board.length; 
        
	    for( int i = 0; i < size; ++i ) { 
	        board[ row ][ i ] += increment; 	
	        board[ i ][ col ] += increment;
    	}
        for( int i = row, j = col; i < size && j < size; ++i, ++j )
            board[ i ][ j ] += increment;
        for( int i = row, j = col; i >= 0 && j >= 0; --i, --j )
            board[ i ][ j ] += increment;
        for( int i = row, j = col; i < size && j >= 0; ++i, --j )
            board[ i ][ j ] += increment;
        for( int i = row, j = col; i >= 0 && j < size; --i, ++j )
            board[ i ][ j ] += increment;
        if( increment == 1 )
	        board[row][col]  = -increment;
        else 
            board[row][col] = 0;
    }

    //Adds a queen to the board updating it.
    private static void addQueen( int row, int col ) {
        update( row, col, 1 );
    }

    //Removes a queen from the board updating it.
    private static void removeQueen( int row, int col ) {
        update( row, col, -1 );
    }

    private static int numOpenSpots() {
        int count = 0;
        for( int i = 0; i < board.length; ++i )
            for( int j = 0; j < board.length; ++j )
                if( board[ i ][ j ] == 0 ) //Open spots
                    ++count;
        return count;
    }

    private static int numQueensOnBoard() {
        int count = 0;
        for( int i = 0; i < board.length; ++i )
            for( int j = 0; j < board.length; ++j )
                if( board[ i ][ j ] == -1 ) //Queen in place.
                    ++count;
        return count;
    
    }

    private static int getOpenSpotRow( int k ) {
        int count = -1;
        for( int i = 0; i < board.length; ++i )
            for( int j = 0; j < board.length; ++j ) {
                if( board[ i ][ j ] == 0 )
                    ++count;
                if( count == k )
                    return i;
            }
        return -99;
    
    }
    
    private static int getOpenSpotCol( int k ) {
        int count = -1;
        for( int i = 0; i < board.length; ++i )
            for( int j = 0; j < board.length; ++j ) {
                if( board[ i ][ j ] == 0 )
                    ++count;
                if( count == k )
                    return j;
            }
        return -99;
    
    }
    
    //for testing purposes
    public static void printBoardtest() {
        for( int i = 0; i < board.length; ++i ) {
            for( int j = 0; j < board.length; ++j )
            {
                if( board[i][j] == -1 )
                    System.out.print( "Q" );
                else
                    System.out.print( board[ i ][ j ] );
            }
            System.out.println();
        }
    }

    //displays board with Queens only.
    public static void printBoard() {
        for( int i = 0; i < board.length; ++i ) {
            for( int j = 0; j < board.length; ++j )
            {
                if( board[i][j] == -1 )
                    System.out.print( " Q " );
                else
                    System.out.print( " - " );
            }
            System.out.println();
        }
    }

    public static void main( String[] args ) {
        int n = 10;
        nQueens newgame = new nQueens( n );
        placeQueens();
        printBoard();      
    }
}