ChessMoves

PROBLEM STATEMENT

Chess is an ancient game played on a board with 64 discrete positions, arranged
in an 8x8 grid.  Each player starts with 16 pieces of a specific color - one
player's pieces are all white (the "white player"), the others are all black
(the "black player").  Players alternate taking turns.  During each turn, the
player can move one of his own pieces in a piece-specific manner.  No piece can
ever occupy more than one position at a time.  Two pieces can never occupy the
same position at one time.  Opponents' pieces can be "taken" by one of the
player's pieces and removed from the game by moving the player's piece into the
position of the of that opponent's piece.  The goal is to threaten the
opponent's king in such a way that he can not escape the threat (checkmate).

Each player starts with 8 pawns - which start the game filling the
second-closest row to the player.  Pawns may move forward (that is: away from
their player's side) one position, if that next position is empty.  Pawns may
also move forward two positions, if both spaces ahead of them are empty and the
pawn is still in its original position (that is, it has not yet moved this
game), at the player's option.  Pawns may not take enemy pieces that are
directly in front of them.  However, if an enemy piece is immediately
diagonally in front of it (that is: one space forward, and one space left or
right), the pawn may opt to move diagonally and take this piece.

Each player starts with 2 knights.  Knights may move 2 spaces in any one
straight direction (that is: forward, backward, left or right), followed by 1
space in a perpendicular direction.  This path need not be clear of pieces, and
the target area must be empty, or contain an enemy piece (which is taken if the
knight moves there).  The knights are the only pieces in the game that can jump
over other pieces and don't need a clear path in order to move.

Each player starts with 2 rooks.  Rooks may move any number of unoccupied
positions in any one straight direction (that is: forward, backward, left or
right).  They may also take an enemy piece if there is an unblocked path in a
straight direction from the rook to that piece.

Each player starts with 2 bishops.  Bishops may move any number of unoccupied
positions in any one diagonal direction (that is: forward-left, backward-left,
forward-right or backward-right).  They may also take an enemy piece if there
is an unblocked path in a diagonal direction from the bishop to that piece.

Each player starts with 1 queen.  Queens may move any number of unoccupied
positions in any one diagonal or straight direction (that is: forward,
backward, left, right, forward-left, backward-left, forward-right or
backward-right).  They may also take an enemy piece if there is an unblocked
path in a straight or diagonal direction from the queen to that piece.

Each player has 1 king.  Kings may move to any one unoccupied position that is
adjacent in any one diagonal or straight direction (that is: forward, backward,
left, right, forward-left, backward-left, forward-right or backward-right).
They may also take an enemy piece that is in any one unoccupied position that
is adjacent in any one diagonal or straight direction from the king.

If the opponent has a valid move which would take the player's king, the king
is said to be in "check".  The player is never allowed to make a move which
leaves his king in check.  This also implies that if the player's king is in
check, the player MUST make a move that gets his king out of check.  No moves
that fail to do this can be made.

Create a class ChessMoves that contains the method number, which takes a
String[] board and, for each player, returns the total number of possible moves
that can legally be made if it is that player's turn, or -1 if the opponent of
that player is already in check.  This answer should be returned as an int[]
with the first element for the black player and the second element for the
white player.

The board will be represented as a String[] - with each element representing a
row of the board, row 0 (zero) being the row closest to the black player, and
row 7 (seven) being the row closest to the white player.  Each element will
contain exactly one character for each location on the board, in order from
left to right.  Empty locations will be represented by a period ('.').  Black
pieces will be represented by capital letters.  White pieces will be
represented by lower-case letters.  Kings are represented by 'K' and 'k',
queens by 'Q' and 'q', knights by 'N' and 'n', bishops by 'B' and 'b', rooks by
'R' and 'r', and pawns by 'P' and 'p'.

DEFINITION
Class: ChessMoves
Method: number
Parameters: String[]
Returns: int[]
Method signature (be sure your method is public):  int[] number(String[] board);


NOTES
- For those who know chess, pawn promotions, en passant, castling, and
stalemates are not included.  Pawns simply stop if they reach the opponent's
edge of the board.
- The board will not necessarily represent a truly valid chess game state - for
example, a player may have two bishops on the same diagonal even though this is
impossible in normal chess.  Only the limitations listed in the "TopCoder will
ensure" section (below) will be enforced.  Read them carefully and assume
nothing else.
- Note that 'K' stands for king, not knight.  'N' stands for knight.  Each type
of piece other than a knight is represented by its first letter.
- A piece can put the opponent's king in check even if moving that piece to
actually take the opponent's king would expose your own king to check from one
of the opponent's pieces (see example #1 for clarification).


TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
- board will have exactly 8 elements.
- each element of board will be exactly 8 characters in length.
- board will contain exactly 1 king of each color ('K' and 'k').
- board will not contain more than 1 queen of each color ('Q' and 'q').
- board will not contain more than 2 knights of each color ('N' and 'n').
- board will not contain more than 2 bishops of each color ('B' and 'b').
- board will not contain more than 2 rooks of each color ('R' and 'r').
- board will not contain more than 8 pawns of each color ('P' and 'p').
- Each element of board will contain only the characters 'K', 'Q', 'N', 'B',
'R', 'P', 'k', 'q', 'n', 'b', 'r', 'p' and period ('.').
- Black pawns will never be in row 0.
- White pawns will never be in row 7.
- The board will not be arranged such that both players' kings are in check.

EXAMPLES

(1)
board =
{".K..R...","........","........","....q...","........","........","....k...",".
......."}
returns: {5,-1}
This board looks like this:
	. K . . R . . .
	. . . . . . . .
	. . . . . . . .
	. . . . q . . .
	. . . . . . . .
	. . . . . . . .
	. . . . k . . .
	. . . . . . . .


The black king ('K') is in check - because the white queen ('q') can take it -
even though if the white queen ('q') were to actually move and take the black
king, the black rook ('R') would have the white king ('k') in check.  Thus,
while moving the queen would normally be an illegal move (since you can't move
such that you place your king into check), it may still place the opponent's
king in check.  The black player must move to get out of check - he can move
his rook to kill the white queen, or can move his king left, left-forward,
forward, or right - for a total of 5 possible moves.

(2)
board =
{"RNBQKBNR","PPPPPPPP","........","........","........","........","pppppppp","r
nbqkbnr"}
returns: {20,20}
This is the standard starting position.  Each player can move any one of his 8
pawns in one of two ways, or either one of his two knights in one of two ways
as well - totalling 20 possible opening moves.

(3)
board =
{"RNBQKBNR",".PPPPPPP","........","........","........","........","pppppppp","r
nbqkbnr"}
returns: {24,20}
Removing the right-most black pawn from example 1 reduces the number of pawn
moves available to the black player by two, but allows him to move his rook to
any one of 6 possible locations.

(4)
board =
{".NBQKBNR",".PPPPPPP","........","....R...","........","........","pppp.ppp","r
nbqkbnr"}
returns: {-1,3}
The black player has the white player in check, and the white player has only 3
possible moves that can get him out of it.  He can move his queen or his
right-most bishop to block the attack, or he can block the attack with his
right-most knight.

(5)
board =
{".K......","........",".......P","........","........","........","........","q
rrk...."}
returns: {0,-1}
The white player has the black player in check which he can not escape
(checkmate).

(6)
board =
{".K......","..Q.....","...b....","........","........","........","........",".
.k....."}
returns: {-1,6}

(7)
board =
{".K......","..Q.....","...b....","........","........","........","........",".
....k.."}
returns: {5,15}