public class  board  {


    private static int  noQueen = 0;


    private int  size;
    private int  used;

    private int      column[];

    private boolean  freeColumn[];
    private boolean  freeDownDiagonal[];
    private boolean  freeUpDiagonal[];


    public  board ( int n )  {

        int i;
        int diags = 2*n - 1;

        size = n;
        used = 0;

        column           = new int     [ size  ];

        freeColumn       = new boolean [ size  ];
        freeDownDiagonal = new boolean [ diags ];
        freeUpDiagonal   = new boolean [ diags ];

        for  ( i = 0;  i < size;  i++ )  {

            column[i]     = noQueen;
            freeColumn[i] = true;
          }

        for  ( i = 0;  i < diags;  i++ )  {

            freeDownDiagonal[i] = true;
            freeUpDiagonal[i]   = true;
          }
      }


    private int  rowIdx ( int i )  {

        return ( i - 1 );
      }

    private int  colIdx ( int i, int j )  {

        return ( j - 1 );
      }

    private int  downDiagIdx ( int i, int j )  {

        return ( i - j + size - 1 );
      }

    private int  upDiagIdx ( int i, int j )  {

        return ( i + j - 2 );
      }


    public int  getSize ()  {

        return ( size );
      }


    public boolean  success ()  {

        return ( used == size );
      }


    public boolean  safeNextPosition ( int j )  {

        int i = used + 1;

        return ( freeColumn[ colIdx(i,j) ]            &
                 freeDownDiagonal[ downDiagIdx(i,j) ] &
                 freeUpDiagonal[ upDiagIdx(i,j) ]       );
      }


    public void  putNextQueen ( int j )  {

        if  ( safeNextPosition(j) & (used < size) )  {

            int i = used + 1;

            used = i;

            column[ rowIdx(i) ] = j;

            freeColumn[ colIdx(i,j) ]            = false;
            freeDownDiagonal[ downDiagIdx(i,j) ] = false;
            freeUpDiagonal[ upDiagIdx(i,j) ]     = false;
          }
      }


    public void  removeLastQueen ()  {

        if  ( used > 0 )  {

            int i = used;
            int j = column[ rowIdx(i) ];

            used = i - 1;

            column[ rowIdx(i) ] = noQueen;

            freeColumn[ colIdx(i,j) ]            = true;
            freeDownDiagonal[ downDiagIdx(i,j) ] = true;
            freeUpDiagonal[ upDiagIdx(i,j) ]     = true;
          }
      }


    public void  showBoard()  {

        int i, j;

        System.out.println( "" );

        for  ( i = 1;  i <= size;  i++ )  {

            System.out.print("  ");

            for  ( j = 1;  j <= size;  j++ )  {

                if  (column[ rowIdx(i) ] == j)  {

                    System.out.print("X");
                  }
                else  {

                    System.out.print("O");
                  }
             }

            System.out.println( "" );
          }

        System.out.println( "" );
      }

  }