import java.io.*;

/**
 * This class is used to solve a generalized version of the Eight Queens Problem.
 * The solution deviates slightly from the problem statement in that the method
 * checkForAttacks now returns a boolean that is true if an attack exists, and
 * false otherwise (as well as printing out the required statement).
 * 
 * @author Liam Keliher + Andy Hebert (setQueens method)
 * @version 14-Nov-2005
 */
public class QueensProblemSolution
{
    public static final int MAX_DIMEN = 12;
    public static final int MIN_DIMEN = 2;
    public static final int DEFAULT_DIMEN = 8;
    private int dimen;
    private boolean[][] board;
    //---------------------------------------------------------------
    public QueensProblemSolution(int inDimen)
    {
        if ((inDimen < MIN_DIMEN) || (inDimen > MAX_DIMEN))
        {
            dimen = DEFAULT_DIMEN;
        } // if
        else
        {
            dimen = inDimen;
        } // else

        board = new boolean[dimen][dimen];
    } // constructor QueensProblemSolution(int)
    //---------------------------------------------------------------
    public void addQueen(int row, int col)
    {
        if ((row < 0) || (row >= dimen) || (col < 0) || (col >= dimen))
        {
            System.out.println("Bad queen position: (" + row + "," + col + ")");
        } // if
        else if (board[row][col])
        {
            System.out.println("Valid board position, but already occupied");
        } // else if
        else
        {
            board[row][col] = true;
        } // else
    } // addQueen(int,int)
    //---------------------------------------------------------------
    public void removeQueen(int row, int col)
    {
        if ((row < 0) || (row >= dimen) || (col < 0) || (col >= dimen))
        {
            System.out.println("Bad queen position: (" + row + "," + col + ")");
        } // if
        else if (!board[row][col])
        {
            System.out.println("Valid board position, but no queen to remove");
        } // else if
        else
        {
            board[row][col] = false;
        } // else
    } // removeQueen(int,int)
    //---------------------------------------------------------------
    private void printLine()
    {
        for (int i = 0; i < 4*dimen+1; i++)
        {
            System.out.print("-");
        } // for i
        System.out.println();
    } // printLine()
    //---------------------------------------------------------------
    public void printBoard()
    {
        int row, col;
        
        for (int i = 0; i < 10; i++)
        {
            System.out.println("\n");
        } // for i

        printLine();
        for (row = 0; row < dimen; row++)
        {
            for (col = 0; col < dimen; col++)
            {
                System.out.print("| " + (board[row][col] ? 'Q' : ' ') + " ");
            } // for col
            System.out.println("|");
            printLine();
        } // for row
    } // printBoard()
    //---------------------------------------------------------------
    public boolean checkForAttacks()
    {
        int row, col, count;
        boolean existsAttack = false;

        //--- Check that no row has 2 or more queens ---
        for (row = 0; !existsAttack && (row < dimen); row++)
        {
            count = 0;
            for (col = 0; !existsAttack && (col < dimen); col++)
            {
                if (board[row][col])
                {
                    count++;
                    if (count >= 2)
                    {
                        existsAttack = true;
                    } // if
                } // if
            } // for col
        } // for row

        //--- Check that no column has 2 or more queens ---
        for (col = 0; !existsAttack && (col < dimen); col++)
        {
            count = 0;
            for (row = 0; !existsAttack && (row < dimen); row++)
            {
                if (board[row][col])
                {
                    count++;
                    if (count >= 2)
                    {
                        existsAttack = true;
                    } // if
                } // if
            } // for row
        } // for col


        //--- Check diagonals running NW-SE ---
        for (col = 0; !existsAttack && (col < (dimen-1)); col++)
        {
            if (countSE(0, col) >= 2)
            {
                existsAttack = true;
            } // if
        } // for col        
        for (row = 1; !existsAttack && (row < (dimen-1)); row++)
        {
            if (countSE(row, 0) >= 2)
            {
                existsAttack = true;
            } // if
        } // for row


        //--- Check diagonals running NE-SW ---
        for (col = 1; !existsAttack && (col < dimen); col++)
        {
            if (countSW(0, col) >= 2)
            {
                existsAttack = true;
            } // if
        } // for col
        for (row = 1; !existsAttack && (row < (dimen-1)); row++)
        {
            if (countSW(row, dimen-1) >= 2)
            {
                existsAttack = true;
            } // if
        } // for row


        //--- The conclusion of the matter ---
        if (existsAttack)
        {
            System.out.println("\nYES, two or more queens can attack each other.");
        } // if
        else
        {
            System.out.println("\nNO, there are no attacks.");
        } // else
        
        return existsAttack;
    } // checkForAttacks()
    //---------------------------------------------------------------
    /**
     * Counts the number of queens on the diagonal starting at the
     * specified position and heading south-east.  If the starting
     * position is not on the board, returns 0.
     */
    private int countSE(int inRow, int inCol)
    {
        int row = inRow, col = inCol, count;

        if ((row < 0) || (row >= dimen) || (col < 0) || (col >= dimen))
        {
            return 0;
        } // if

        count = 0;
        while ((row < dimen) && (col < dimen))
        {
            if (board[row][col])
            {
                count++;
            } // if
            row++;
            col++;
        } // while

        return count;
    } // countSE(int,int)
    //---------------------------------------------------------------
    /**
     * Counts the number of queens on the diagonal starting at the
     * specified position and heading south-west.  If the starting
     * position is not on the board, returns 0.
     */
    private int countSW(int inRow, int inCol)
    {
        int row = inRow, col = inCol, count;

        if ((row < 0) || (row >= dimen) || (col < 0) || (col >= dimen))
        {
            return 0;
        } // if

        count = 0;
        while ((row < dimen) && (col >= 0))
        {
            if (board[row][col])
            {
                count++;
            } // if
            row++;
            col--;
        } // while

        return count;
    } // countSW(int,int)
    //---------------------------------------------------------------
    /**
     *  This method tries to place the same number of queens on the board as there
     *  are rows/columns, while ensuring that no two queens can attack each other.
     */
    public void setQueens()
    {
        int numQueens = 0;  // number of queens places so far, and also row we are currently working on
        int col = 0;        // the column (of the current row) in which we are trying to place a queen

        while(true)
        {
            if(numQueens == dimen)      // problem is solved!
            {
                 printBoard();
                 return;
            }// end if

            addQueen(numQueens, col);
            if(!checkForAttacks())      // if queens places so far are OK, go to next row
            {
                 numQueens++;
                 col = 0;
                 continue;
            }//end if
            else if(col+1 < dimen)      // there is an attack, so remove queen and try one square over
            {
                 removeQueen(numQueens, col);
                 col++;
                 continue;
            }// end else if
            else                        // end of row and we could not place a queen, so back up one row
            {
                  removeQueen(numQueens, col);       // remove current queen
                  numQueens--;                       // move up one row
                  for(int i = 0; i < dimen; i++)
                  {
                      if(board[numQueens][i])        // find queen in current row
                      {
                           removeQueen(numQueens, i);              // remove queen and try to move one square over
                           if((i == dimen-1) && (numQueens !=0))   // if current queen is at end of row
                           {
                                col = 0;
                                numQueens--;                // move up one row
                                i = -1;                     // restarts the for loop to find queen in current row
                                continue;
                           }// end if
                           else if((i == dimen-1) && (numQueens == 0))  // if first queen at end of first row then no possible solution
                           {
                                System.out.println("There are no possible combinations");
                                return;
                           }// end else if
                           col = i+1;
                           break;
                       }// end if
                  }// end for
             }// end else
        }// end while

    }// end setQueens()
    //---------------------------------------------------------------
} // class QueensProblemSolution