/*
 * DeeperBlueDriver.java
 *
 * Created on July 23, 2001, 10:25 AM
 */

import java.io.*;
import java.util.*;

/**
 *
 * @author Chris Schmidt
 */
public class DeeperBlueDriver {

    /** Creates new DeeperBlueDriver */
    public DeeperBlueDriver() {
    }

/**
 * Starts the application.
 * @param args an array of command-line arguments
 */
public static void main(java.lang.String[] args) {
        int height = 0, width = 0, loop, col, iPieceCount = 0;
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        Board board;
        ChessPieceFactory fac = new ChessPieceFactory();
        ChessPiece piece;
        String sTemp = "EMPTY";
        
        // Read the information from standard in         
        try {
            while (sTemp != null && sTemp.trim().compareTo("") != 0) {
                // Begin with START
                sTemp = buf.readLine();
                if (sTemp != null && sTemp.trim().compareTo("") != 0) {
                    // The total count of pieces removed from the board
                    iPieceCount = 0;
                    // First line is width
                    width = new Integer(buf.readLine()).intValue();

                    // Second line is the height
                    height = new Integer(buf.readLine()).intValue();

                    // Create the Board
                    board = new Board(height, width);
                    board.cleanBoard();
                
                    // Place the pieces
                    for (loop = 0; loop < height; loop++) {
                        // Should only have to loop *height* number of times to get all information
                        sTemp = buf.readLine();
                        // Break the line into tokens and try to create a chess piece based on that token
                        StringTokenizer st = new StringTokenizer(sTemp);

                        col = 0;
                        while(st.hasMoreTokens()) {
                                String item = st.nextToken();
                                
                                // Create the Chess Piece
                                piece = fac.createPiece(item);

                                // Place this piece into (row,col) in the board
                                board.placePiece(piece,loop,col);
                                col++;
                        }
                    }

                // Last line should be END
                sTemp = buf.readLine();
                
                // Write out the number of pieces found that need to be removed
                System.out.println("Minimum Number of Pieces to be removed: " + board.minRemovedPieces());
                }
            }
        } catch (IOException ioerr) {
                // Caught a fatal error.  Print the stack trace and exit
                ioerr.printStackTrace();
        }
        
}    
}

/**
 * Representation of a chess board.  Pieces use the board to determine their position, calculate what they
 * can attack, and what pieces hit them.  
 * Creation date: (7/26/01 8:01:45 AM)
 * @author: Chris Schmidt
 */
class Board {
        /** 2D Array comprising the board of Chess pieces */
        private ChessPiece [][] brd;
        /** Internal variable to count the total number of iterations used during the calculation */
        private int iters = 0;   
        /** array that is the size of all possible iterations that could happen */
        private boolean [] traversed = null;
        
        /**
         * Board constructor -- Builds the chess board to the size given.
         * @param height Height of the chess board (1..10)
         * @param width Width of the board (1..10)
         */
public Board(int height, int width) {
        super();
        
        brd = new ChessPiece[height][width];
        //traversed = new boolean[33554432];
        cleanBoard();
}
/**
 * Resets the board to empty (no chess pieces).
 * Creation date: (7/26/01 8:27:31 AM)
 */
public void cleanBoard() {
        int loop, loop2;
        
        for (loop = 0; loop < brd.length; loop++) {
                for (loop2 = 0; loop2 < brd[loop].length; loop2++) {
                        brd[loop][loop2] = null;
                }
        }
}

/**
 * Used for debugging purposes, prints out the board as it currently is (including
 * visible and hidden pieces)
 * Creation date: (7/26/01 11:22:06 AM)
 */
public void debugPrint() 
{
        int loop, loop2;
        ChessPiece piece;

        System.out.println("DEBUG --- BEGIN");
        for (loop = 0; loop < brd.length; loop++) {
                for (loop2 = 0; loop2 < brd[loop].length; loop2++) {
                    piece = brd[loop][loop2];
                    if (piece != null) {
                        if (!piece.isHidden()) {
                            System.out.print(piece.getAbbreviation() + "\t");
                        } else {
                            System.out.print("*" + "\t");
                        }
                    } else {
                       System.out.print(".\t");
                    }
                }
                System.out.println("");
        }       
        for (loop = 0; loop < brd.length; loop++) {
                for (loop2 = 0; loop2 < brd[loop].length; loop2++) {
                        piece = brd[loop][loop2];

                        if (piece != null) {
                                System.out.println(piece + ":\t\t[" + loop + "," + loop2 + "]: Attack = " + piece.getAttackCount() + ", Hit = " + piece.getHitCount() + ", Remove = " + piece.getRemoveCount() + ". Hidden = " + piece.isHidden());
                        }
                }
        }
        System.out.println("DEBUG --- END");
}
/**
 * Returns the height of the board.
 * Creation date: (7/26/01 1:25:49 PM)
 * @return int
 */
public int getHeight() {
        return brd.length;
}
/**
 * Takes a 2D coordinate and returns the ChessPiece corresponding to the position.
 * Creation date: (7/26/01 8:31:09 AM)
 * @return com.ibm.deeperblue.ChessPiece
 * @param position int[]
 */
public ChessPiece getPiece(int[] position) {
        ChessPiece result = null;

        // Check for out of bounds
        if (position[0] > -1 && position[0] < brd.length && position[1] > -1 && position[1] < brd[position[0]].length) {
                result = brd[position[0]][position[1]];
        }
        
        return result;
}
/**
 * Returns the position of the supplied Chess piece, (-1,-1) if piece wasn't found.
 * Creation date: (7/26/01 8:28:36 AM)
 * @return java.lang.Integer[]
 * @param piece com.ibm.deeperblue.ChessPiece
 */
public int[] getPosition(ChessPiece piece) {
        int[] result = new int[2];
        int loop, loop2;
        // Set default values for return value
        result[0] = -1;
        result[1] = -1;

        // Go through the board looking for the ChessPiece that is equal to the one passed into the method
        for (loop = 0; loop < brd.length; loop++) {
                for (loop2 = 0; loop2 < brd[loop].length; loop2++) {
                        if (piece.equalsComplete(brd[loop][loop2])) {
                                result[0] = loop;
                                result[1] = loop2;
                        }
                }
        }
        
        return result;
}
/**
 * Returns the width of the board.
 * Creation date: (7/26/01 1:25:49 PM)
 * @return int
 */
public int getWidth() {
        return brd[0].length;
}
/**
 * Returns true if no pieces can attack each other.  Re-calculates all chess piece attacks/hits/etc
 * Creation date: (7/26/01 8:36:24 AM)
 * @return boolean
 */
public boolean isClear() {
        boolean result = true;
        int loop, loop2;
        ChessPiece piece;
        
        // Reset each chess piece in the array back to zero attacks/hits/etc
        for (loop = 0; loop < brd.length; loop++) {
                for (loop2 = 0; loop2 < brd[loop].length; loop2++) {
                        piece = brd[loop][loop2];
                        if (piece != null) {
                                piece.clear();
                        }
                }
        }

        // Re-calculate the values of the attack/hit/etc
        for (loop = 0; loop < brd.length; loop++) {
                for (loop2 = 0; loop2 < brd[loop].length; loop2++) {
                        piece = brd[loop][loop2];
                        if (piece != null && !piece.isHidden()) {
                                piece.doCalculation(this);
                                //debugPrint();
                                // If any piece can attack another piece, then the board isn't "clear" yet
                                if (piece.getAttackCount() > 0) {
                                        result = false;
                                }
                        }
                }
        }
        
        return result;
}

/**
 * Place the chess piece into the 2D array if it isn't a null value
 * Creation date: (7/26/01 9:28:25 AM)
 * @param piece com.ibm.deeperblue.ChessPiece
 * @param row int
 * @param col int
 */
public void placePiece(ChessPiece piece, int row, int col) {
        if (piece != null) {
                brd[row][col] = piece;
        }
}

/**
 * Wrapper for the method that recursively tries to determine the minimum
 * number of chess pieces to remove from the board such that
 * no chess piece can attack another piece.
 * @return int
 */
public int minRemovedPieces() {
    int result = 25000; // Set to some huge number
    int loop, loop2;
    ChessPiece piece;
    
    int totPieces = 0;
    for (loop = 0; loop < brd.length; loop++) {
        for (loop2 = 0; loop2 < brd[loop].length;loop2++) {
            if (brd[loop][loop2] != null) {
                totPieces++;
            }
        }
    }
    
    // Define the traversed boolean array and clear it to false
    try {
        traversed = new boolean[(int)Math.pow(2,totPieces)];
        for (loop = 0; loop < traversed.length; loop++) {
            traversed[loop] = false;
        }
    } catch (java.lang.OutOfMemoryError err) {
        // Could not allocate the memory most probably, do not use the boolean array then
        // -- This will make the calculation VERY slow
        traversed = null;
    }
    
    // Set all chess pieces to visible (or not hidden)
    for (loop = 0; loop < brd.length; loop++) {
        for (loop2 = 0; loop2 < brd[loop].length; loop2++) {
            piece = brd[loop][loop2];
            if (piece != null) {
                piece.setHidden(false);
            }
        }
    }
    
    // The board is in its original configuration check to see if it is already clear
    if (this.isClear()) {
        // No pieces are attacking each other, return immediatly
        result = 0;
    } else {
        // There is at least one piece that will need to be removed. 
        result = minRemovedPieces(0,result);
    }
    
    return result;
}

/**
 * The actual method that finds the minimum pieces to remove
 * @return int
 * @param curDepth Current depth in the decision tree
 * @param bestResult best solution (minimum) thus far in the operation
 */
public int minRemovedPieces(int curDepth,int bestResult) {
    int result = 25000, tempResult = 25000;
    int loop, loop2;
    int iMaxScore = -1;
    int [] pos = new int[2];
    long lTraversedNum;
    ChessPiece piece;
    Vector pieceVec = new Vector();
    // Single sorted tree to hold each piece during the iterations
    // -- Ranked by their score
    TreeSet sortedList = new TreeSet();
    
    iters++;
    
    // Check to see if the board is clear *or* if the current depth surpasses the best result
    // thus far (i.e. already found a better case, no point finding a worse solution)
    if (curDepth == bestResult || this.isClear() ) {
        result = curDepth;
    } else {                
        // Step through each piece that is able to attack another one to see
        //  what the min number of pieces is. 
        
        // Build a vector of the pieces, from the piece with the highest "score" to the lowest.
        // -- I term score by the total number of pieces it can/could hit and those pieces that
        // can hit it
        // The method isClear() has already been called, meaning that each piece has the information needed
        // -- The reason for storing all pieces in the vector is because once I recurse through each possible
        //    outcome, the scores for the pieces change...          
        for (loop =  0; loop < getHeight(); loop++) {
            for (loop2 = 0; loop2 < getWidth(); loop2++) {
                pos[0] = loop;
                pos[1] = loop2;
                piece = getPiece(pos);
                if (piece != null && !piece.isHidden() && (piece.getScore() > 0)) {              
                    sortedList.add(piece);
                }
            }
        }
        
        // Have the sorted list, step through it
        Iterator iter;
        iter = sortedList.iterator();
            
        while (iter.hasNext()) {
            piece = (ChessPiece)iter.next();
                
                piece.setHidden(true);
                lTraversedNum = getPieceConfigurationNum();
                
                // If the boolean array could not be allocated, don't try to calculate if we have visited
                // this configuration of chess pieces.  It will cause the program to go *much* slower
                // because the algorithm using the 'score' can generate the same configuration 
                // multiple times
                if ((lTraversedNum == -1) || (traversed[(int)lTraversedNum] == false)) {
                    
                    if (lTraversedNum != -1) {
                        traversed[(int)lTraversedNum] = true;
                    }
                    
                    pos = getPosition(piece);            
                    tempResult = minRemovedPieces(curDepth+1,bestResult);                           
                } else {
                    // Already hit this combination of chess pieces, we don't want to go through that portion
                    // of the tree again.
                }
                
                piece.setHidden(false);
                if (tempResult < bestResult) {
                    // Found a better path                    
                    result = tempResult;
                    bestResult = tempResult;
                
                }                            
        }
    }
    // If we got here and the result is still 25000, then something bad happened   
    
    return result;
}

/**
 * Returns the total number of pieces that exist on the board at the current time. This does
 * not include pieces that are 'hidden'
 * @return int
 */
public int getPieces() {
    int loop,loop2;
    int [] pos = new int[2];
    ChessPiece piece;
    int result = 0;
    for (loop =  0; loop < getHeight(); loop++) {
            for (loop2 = 0; loop2 < getWidth(); loop2++) {
                pos[0] = loop; pos[1] = loop2;
                piece = getPiece(pos);
                if (piece != null && !piece.isHidden()) {
                    result++;
                }
            }
    }
    return result;
}

/**
 * For each configuration of chess pieces, you can consider it as a binary number (with 'hidden' representing
 * 0 and not-hidden as 1.  Thus, for any given configuration of the chess pieces, we can determine the number
 * it represents and return it
 * @return long
 */
private long getPieceConfigurationNum() {
    int loop,loop2,curPiece = 0;
    ChessPiece piece;
    long result = 0;
    
    if (traversed != null) {
        for (loop = 0; loop < getHeight(); loop++) {
            for (loop2 = 0; loop2 < getWidth(); loop2++) {
                if (brd[loop][loop2] != null) {
                    piece = (ChessPiece)brd[loop][loop2];
                    if (!piece.isHidden()) {
                        result = result + (long)(Math.pow(2,curPiece));
                    }
                    curPiece++;
                }
            }
        }
    } else {
        result = -1;
    }
    //System.out.println("Final number for configuration = " + result);
    return result;
}

}


/**
 * Base class for all chess pieces.
 * Creation date: (7/26/01 8:00:06 AM)
 * @author: Chris Schmidt
 */
abstract class ChessPiece implements java.util.Comparator, Comparable {
        // internal variables used to calculate how many pieces this chess piece would hit, and how many other
        // pieces will hit it.
        //
        // Note:  I also calculate how many pieces would be hit *beyond* this piece if the piece is removed

    /** Number of pieces this piece can attack directly
     */    
        protected int iAttackCount;
        /** Number of pieces that can attack this piece directly
         */        
        protected int iHitCount;
        /** Number of pieces that this piece can attack indirectly (ie the number of pieces
         * that could be hit if interveaning pieces were removed)
         */        
        protected int iRemoveCount;
        /** Represents if the piece is 'hidden' or temporarily removed from the board
         * for calculation purposes
         */        
        protected boolean bHidden;
        
        // The piece's name
        /** Full name of the chess piece
         */        
        protected String sPieceName;
/**
 * ChessPiece constructor comment.
 */
public ChessPiece() {
        super();

        iAttackCount = 0;
        iHitCount = 0;
        iRemoveCount = 0;
        bHidden = false;
}
/**
 * Resets the internal count variables back to zero.
 * Creation date: (7/26/01 8:11:57 AM)
 */
public void clear() {
        iAttackCount = 0;
        iHitCount = 0;
        iRemoveCount = 0;
}
/**
 * Force the chess piece to calculate what it can attack from the board specified.
 * Creation date: (7/26/01 8:18:48 AM)
 * @param board com.ibm.deeperblue.Board
 */
public abstract void doCalculation(Board board);
/**
 * Returns the count of pieces this piece can attack directly.
 * Creation date: (7/26/01 8:48:40 AM)
 * @return int
 */
public int getAttackCount() {
        return iAttackCount;
}
/**
 * Returns the count of pieces this chess piece can be hit by.
 * Creation date: (7/26/01 8:48:40 AM)
 * @return int
 */
public int getHitCount() {
        return iHitCount;
}
/**
 * Returns the count of pieces that are blocked from being hit by this chess piece.
 * Creation date: (7/26/01 8:48:40 AM)
 * @return int
 */
public int getRemoveCount() {
        return iRemoveCount;
}
/**
 * Increments this pieces count that denotes how many pieces it can attack directly.
 * Creation date: (7/26/01 8:13:34 AM)
 */
public void incAttack() {iAttackCount++;}
/**
 * Increments this pieces count that denotes how many pieces can attack it.
 * Creation date: (7/26/01 8:13:34 AM)
 */
public void incHit() {iHitCount++;}
/**
 * Increments this pieces count that denotes how many pieces it is blocking from being hit by another piece.
 * Creation date: (7/26/01 8:13:34 AM)
 */
public void incRemove() {iRemoveCount++;}
/**
 * Sets the chess piece's name to sName.
 * Creation date: (7/26/01 9:59:10 AM)
 * @param sName java.lang.String
 */
public void setName(String sName) {
        this.sPieceName = sName;
}
/**
 * Returns a String that represents the value of this object.
 * @return a string representation of the receiver
 */
public String toString() {
        return sPieceName;
}

/**
 * Sets the internal hidden boolean variable
 * @param bHidden True if the piece should be set to hidden, false otherwise
 */
public void setHidden(boolean bHidden){
    this.bHidden = bHidden;
}
/**
 * Returns whether this chess piece is 'hidden' from the other pieces.  If so, it is not considered
 * to be on the board while calculating if pieces can attack each other.
 * @return boolean
 */
public boolean isHidden() {
    return this.bHidden;
}

/**
 * Returns the abbreviation of the current chess piece (as opposed to the full name)
 * @return String
 */
public abstract java.lang.String getAbbreviation();

/**
 * Returns the 'score' of a particular chess piece. The score is defined as the
 * total number of pieces that it can hit, and the number that hit it. The 
 * chances are great that a piece with a high 'score' is probably a piece that
 * should be removed from the board to ensure a minimum when removing pieces.
 *@return int
 */
public int getScore() {
    return this.getAttackCount() + this.getHitCount() + this.getRemoveCount();
}

/**
 * Compares two objects and returns an int based on which chess piece is 'larger'.
 * Here, larger means which piece has the higher score.
 * @return int
 * @param obj1 First object to compare
 * @param obj2 object to compare to the first
 */
public int compare(Object obj1, Object obj2) {
    ChessPiece piece1, piece2;
    int score1, score2;
    int result = 0;
    
    piece1 = (ChessPiece)obj1;
    piece2 = (ChessPiece)obj2;
    
    score1 = piece1.getScore();
    score2 = piece2.getScore();
    
    if (score1 != score2) {
        result = (score2 - score1)/Math.abs(score2 - score1);   
    }
    
    return result;
}

/**
 * Checks to see if the two objects are the exact same object, not just a similar
 * object with the same characteristics
 * @return boolean
 * @param obj Object to compare this object to for equality
 */
public boolean equalsComplete(Object obj) {
    boolean result = false;
    
    if (this == obj) {
        result = true;
    }
    
    return result;
}

/**
 * Compares two chess pieces to determine if they are equal in nature to each other.
 * (i.e. if their 'score' and names match)
 * @return int
 * @param obj Object to compare this object to
 */
public boolean equals(Object obj) {
    ChessPiece piece1,piece2 = (ChessPiece) obj;
    boolean result = false;
    int score1, score2;
    
    piece1 = this;
    piece2 = (ChessPiece)obj;
    
    score1 = piece1.getScore();
    score2 = piece2.getScore();   
    
    if ((score1 == score2) && piece1.toString().compareTo(piece2.toString()) == 0) {
        result = true;
    }
    
    return result;
}

/**
 * Compares this object with another object to determine if they are equal or if one is
 * larger (based on the objects score) than one another.
 * @return int
 * @param obj Secondary object to compare the current object to
 */
public int compareTo(java.lang.Object obj) {
    return compare(this,obj); 
}

}

/**
 * Responsible for creating the different chess pieces based on an identifier.
 * Creation date: (7/26/01 8:44:59 AM)
 * @author: Chris Schmidt
 */
class ChessPieceFactory {
/**
 * ChessPieceFactory constructor comment.
 */
public ChessPieceFactory() {
        super();
}
/**
 * Creates a specific chess piece based on the identifier sent into the method.
 * Creation date: (7/26/01 8:45:59 AM)
 * @return com.ibm.deeperblue.ChessPiece
 * @param ident java.lang.String
 */
public ChessPiece createPiece(String ident) {
        ChessPiece result = null;

        // Based on the ident, create a known Chess Piece
        if (ident.compareTo("K") == 0) {
                // This is a King Chess Piece
                result = new King();
        } else if (ident.compareTo("N") == 0) {
                // This is a Knight Chess Piece
                result = new Knight();
        } else if (ident.compareTo("R") == 0) {
                // This is a Rook Chess Piece
                result = new Rook();
        } else if (ident.compareTo("B") == 0) {
                // This is a Bishop Chess Piece
                result = new Bishop();
        } else if (ident.compareTo("Q") == 0) {
                result = new Queen();
        }
        
        return result;
}
}

/**
 * The subclass representing a Knight chess piece (Denoted as 'N').
 * Creation date: (7/26/01 12:43:47 PM)
 * @author: Chris Schmidt
 */
class Knight extends ChessPiece {
/**
 * Knight constructor comment.
 */
public Knight() {
        super();
        setName("Knight");
}
/**
 * Force the chess piece to calculate what it can attack from the board specified.
 * Creation date: (7/26/01 12:43:47 PM)
 * @param board com.ibm.deeperblue.Board
 */
public void doCalculation(Board board) {
        int[] curPos, tempPos = new int[2];
        ChessPiece otherPiece;
        int loop, loop2;
        
        // The Knight can hit a square via the 'L' shape attack (two blocks N,E,S,W then 1 block perp. to the line)
        
        // Determine what position this piece is at
        curPos = board.getPosition(this);
        
        // Check each spot the knight can attack (8 positions)
        //      - The positions will be (row +/- 1,col +/- 2 ) & (row +/- 2,col +/- 1)
        for (loop = 0; loop < 4; loop++) {
                for (loop2 = 0; loop2 < 2; loop2++) {
                        // Use 0..3 of loop as the cardinal points N,E,S,W
                        // Use 0,1 of loop2 as right,left; up,down off of the initial 2 block move

                        switch (loop) {
                                case 0: tempPos[0] = curPos[0] - 2;
                                                if (loop2 == 0)
                                                        tempPos[1] = curPos[1] + 1;
                                                else
                                                        tempPos[1] = curPos[1] - 1;
                                                break;  
                                case 1: tempPos[1] = curPos[1] + 2;
                                                if (loop2 == 0)
                                                        tempPos[0] = curPos[0] - 1;
                                                else
                                                        tempPos[0] = curPos[0] + 1;
                                                break;
                                case 2: tempPos[0] = curPos[0] + 2;
                                                if (loop2 == 0)
                                                        tempPos[1] = curPos[1] + 1;
                                                else
                                                        tempPos[1] = curPos[1] - 1;
                                                break;
                                case 3: tempPos[1] = curPos[1] - 2;
                                                if (loop2 == 0)
                                                        tempPos[0] = curPos[0] - 1;
                                                else
                                                        tempPos[0] = curPos[0] + 1;
                                                break;
                        }
                        
                        otherPiece = board.getPiece(tempPos);

                        if (otherPiece != null) {
                                // Don't attack yourself
                                if (!this.equalsComplete(otherPiece) && !otherPiece.isHidden()) {
                                        // Found an attackable chess piece
                                        // Update the knight's attack count
                                        this.incAttack();
                                        // Update the other piece's hit count
                                        otherPiece.incHit();
                                        // Since the knight doesn't 'travel' when attacking a space, disregard the remove count
                                }
                        }
                }
        }       
}

/** Returns an abbreviation of the chess piece (normally the first character
 * unless a conflict occurrs with another chess piece)
 * @return String
 */
public java.lang.String getAbbreviation() {
    return "N";
}

}

/**
 * Insert the type's description here.
 * Creation date: (7/26/01 3:02:45 PM)
 * @author: Administrator
 */
class Queen extends ChessPiece {
/**
 * Queen constructor comment.
 */
public Queen() {
        super();
        setName("Queen");
}
/**
 * Force the chess piece to calculate what it can attack from the board specified.
 * Creation date: (7/26/01 3:02:45 PM)
 * @param board com.ibm.deeperblue.Board
 */
public void doCalculation(Board board) {
        int[] curPos, tempPos = new int[2];
        ChessPiece otherPiece;
        int preloop, loop, loop2;
        int iNDec = 0, iEDec = 0;
        ChessPiece candidate = null;
        
        // The Queen can hit any object in a line diagonal from it (NE,SE,SW,NW), or
        //      on a straight line from it (N,E,S,W)
        
        // Determine what position this piece is at
        curPos = board.getPosition(this);
        
        // Check each spot the Queen can attack
        for (preloop = 0; preloop < 8; preloop++) {
                // Use 0..3 of preloop as the points (NE,SE,SW,NW)
                // 4..7 are the cardinal points (N,S,E,W)
                switch (preloop) {
                        case 0: // Go northeast, from the current position until the edge of the board
                                        iNDec = -1;
                                        iEDec = 1;
                                        break;
                        case 1: // Go southeast
                                        iNDec = 1;
                                        iEDec = 1;
                                        break;
                        case 2: // Go southwest         
                                        iNDec = 1;
                                        iEDec = -1;
                                        break;
                        case 3: // Go northwest
                                        iNDec = -1;
                                        iEDec = -1;
                                        break;
                        case 4: // Go North
                                        iNDec = -1;
                                        iEDec = 0;
                                        break;
                        case 5: // Go East
                                        iNDec = 0;
                                        iEDec = 1;
                                        break;
                        case 6: // Go South
                                        iNDec = 1;
                                        iEDec = 0;
                                        break;
                        case 7: // Go West
                                        iNDec = 0;
                                        iEDec = -1;
                                        break;
                }
                
                candidate = null;
                loop = curPos[0]; loop2 = curPos[1];
                while (loop >= 0 && loop2 >= 0 && loop < board.getHeight() && loop2 < board.getWidth()) {

                        loop = loop + iNDec;
                        loop2 = loop2 + iEDec;
                                
                        tempPos[0] = loop;
                        tempPos[1] = loop2;
                                        
                        otherPiece = board.getPiece(tempPos);

                        if (otherPiece != null) {
                                // Don't attack yourself
                                if (!this.equalsComplete(otherPiece) && !otherPiece.isHidden()) {
                                        // Found an attackable object, Check to see if we have already found the candidate
                                        // (i.e. already found the piece the Queen would normally hit)
                                        if (candidate == null) {
                                                candidate = otherPiece;
                                        } else {
                                                // This object is behind the candidate
                                                this.incRemove();
                                        }
                                }
                        }
                }
                if (candidate != null) {
                        // Found an object that could be attacked during the last 'move'
                        this.incAttack();
                        // Update the other piece's hit count
                        candidate.incHit();
                }       
        }                               
}

/** Returns an abbreviation of the chess piece (normally the first character
 * unless a conflict occurrs with another chess piece)
 * @return String
 */
public java.lang.String getAbbreviation() {
    return "Q";
}

}

/**
 * The subclass representing a Rook chess piece (Denoted as 'R').
 * Creation date: (7/26/01 1:16:06 PM)
 * @author: Chris Schmidt
 */
class Rook extends ChessPiece {
/**
 * Rook constructor comment.
 */
public Rook() {
        super();
        setName("Rook");
}
/**
 * Force the chess piece to calculate what it can attack from the board specified.
 * Creation date: (7/26/01 1:16:06 PM)
 * @param board com.ibm.deeperblue.Board
 */
public void doCalculation(Board board) {
        int[] curPos, tempPos = new int[2];
        ChessPiece otherPiece;
        int preloop, loop, loop2;
        int iNDec = 0, iEDec = 0;
        ChessPiece candidate = null;
        
        // The Rook can hit any object in a straight line from it (N,E,S,W)
        
        // Determine what position this piece is at
        curPos = board.getPosition(this);
        
        // Check each spot the rook can attack
        for (preloop = 0; preloop < 4; preloop++) {
                // Use 0..3 of preloop as the cardinal points (N,E,S,W)
                switch (preloop) {
                        case 0: // Go north, from the current position until the edge of the board
                                        iNDec = -1;
                                        iEDec = 0;
                                        break;
                        case 1: // Go east
                                        iNDec = 0;
                                        iEDec = 1;
                                        break;
                        case 2: // Go south             
                                        iNDec = 1;
                                        iEDec = 0;
                                        break;
                        case 3: // Go west
                                        iNDec = 0;
                                        iEDec = -1;
                                        break;
                }
                
                candidate = null;
                loop = curPos[0]; loop2 = curPos[1];
                while (loop >= 0 && loop2 >= 0 && loop < board.getHeight() && loop2 < board.getWidth()) {

                        loop = loop + iNDec;
                        loop2 = loop2 + iEDec;
                                
                        tempPos[0] = loop;
                        tempPos[1] = loop2;
                                        
                        otherPiece = board.getPiece(tempPos);

                        if (otherPiece != null) {
                                // Don't attack yourself
                                if (!this.equalsComplete(otherPiece) && !otherPiece.isHidden()) {
                                        // Found an attackable object, Check to see if we have already found the candidate
                                        // (i.e. already found the piece the rook would normally hit)
                                        if (candidate == null) {
                                                candidate = otherPiece;
                                        } else {
                                                // This object is behind the candidate
                                                this.incRemove();
                                        }
                                }
                        }
                }
                if (candidate != null) {
                        // Found an object that could be attacked during the last 'move'
                        this.incAttack();
                        // Update the other piece's hit count
                        candidate.incHit();
                }       
        }                               
}

/** Returns an abbreviation of the chess piece (normally the first character
 * unless a conflict occurrs with another chess piece)
 * @return String
 */
public java.lang.String getAbbreviation() {
    return "R";
}

}

/**
 * The subclass representing a King chess piece (Denoted as 'K').
 * Creation date: (7/26/01 9:57:53 AM)
 * @author: Chris Schmidt
 */
class King extends ChessPiece {
        
/**
 * King constructor comment.
 */
public King() {
        super();
        setName("King");
}
/**
 * Force the chess piece to calculate what it can attack from the board specified.
 * Creation date: (7/26/01 9:57:53 AM)
 * @param board com.ibm.deeperblue.Board
 */
public void doCalculation(Board board) {
        int[] curPos, tempPos = new int[2];
        ChessPiece otherPiece;
        int loop, loop2;
        
        // The King can attack one square from itself in any direction.
        
        // Determine what position this piece is at
        curPos = board.getPosition(this);
        
        // Go around the king's position and try to find another piece
        //      - The positions will be (row - 1, col + 1) --> (row + 1, col - 1) besides (row,col)
        for (loop = curPos[0] - 1; loop <= curPos[0] + 1; loop++) {
                for (loop2 = curPos[1] - 1; loop2 <= curPos[1] + 1; loop2++) {
                        tempPos[0] = loop;
                        tempPos[1] = loop2;
                        otherPiece = board.getPiece(tempPos);

                        if (otherPiece != null) {
                                // Don't attack yourself
                                if (!this.equalsComplete(otherPiece) && !otherPiece.isHidden()) {
                                        // Found an attackable chess piece
                                        // Update the king's attack count
                                        this.incAttack();
                                        // Update the other pieces hit count
                                        otherPiece.incHit();
                                        // Since the king can only hit objects one space from it, don't worry about the remove count
                                }
                        }
                }
        }
}

/** Returns an abbreviation of the chess piece (normally the first character
 * unless a conflict occurrs with another chess piece)
 * @return String
 */
public java.lang.String getAbbreviation() {
    return "K";
}

}

/**
 * The subclass representing a Bishop chess piece (Denoted as 'B').
 * Creation date: (7/26/01 2:20:32 PM)
 * @author: Chris Schmidt
 */
class Bishop extends ChessPiece {
/**
 * Bishop constructor comment.
 */
public Bishop() {
        super();
        setName("Bishop");
}
/**
 * Force the chess piece to calculate what it can attack from the board specified.
 * Creation date: (7/26/01 2:20:32 PM)
 * @param board com.ibm.deeperblue.Board
 */
public void doCalculation(Board board) {
        int[] curPos, tempPos = new int[2];
        ChessPiece otherPiece;
        int preloop, loop, loop2;
        int iNDec = 0, iEDec = 0;
        ChessPiece candidate = null;
        
        // The Bishop can hit any object in a line diagonal from it (NE,SE,SW,NW)
        
        // Determine what position this piece is at
        curPos = board.getPosition(this);
        
        // Check each spot the bishop can attack
        for (preloop = 0; preloop < 4; preloop++) {
                // Use 0..3 of preloop as the cardinal points (NE,SE,SW,NW)
                switch (preloop) {
                        case 0: // Go northeast, from the current position until the edge of the board
                                        iNDec = -1;
                                        iEDec = 1;
                                        break;
                        case 1: // Go southeast
                                        iNDec = 1;
                                        iEDec = 1;
                                        break;
                        case 2: // Go southwest         
                                        iNDec = 1;
                                        iEDec = -1;
                                        break;
                        case 3: // Go northwest
                                        iNDec = -1;
                                        iEDec = -1;
                                        break;
                }
                
                candidate = null;
                loop = curPos[0]; loop2 = curPos[1];
                while (loop >= 0 && loop2 >= 0 && loop < board.getHeight() && loop2 < board.getWidth()) {

                        loop = loop + iNDec;
                        loop2 = loop2 + iEDec;
                                
                        tempPos[0] = loop;
                        tempPos[1] = loop2;
                                        
                        otherPiece = board.getPiece(tempPos);

                        if (otherPiece != null) {
                                // Don't attack yourself
                                if (!this.equalsComplete(otherPiece) && !otherPiece.isHidden()) {
                                        // Found an attackable object, Check to see if we have already found the candidate
                                        // (i.e. already found the piece the bishop would normally hit)
                                        if (candidate == null) {
                                                candidate = otherPiece;
                                        } else {
                                                // This object is behind the candidate
                                                this.incRemove();
                                        }
                                }
                        }
                }
                if (candidate != null) {
                        // Found an object that could be attacked during the last 'move'
                        this.incAttack();
                        // Update the other piece's hit count
                        candidate.incHit();
                }
        }
}

/** Returns an abbreviation of the chess piece (normally the first character
 * unless a conflict occurrs with another chess piece)
 * @return String
 */
public java.lang.String getAbbreviation() {
    return "B";
}

}