Given an arbitrary chessboard as standard input (in which each piece is on a square), produce as standard output a list of moves needed to regularize, or set up, the chessboard. The moves need not be legal, yet no piece may be placed above another. The program must warn about any missing or additional pieces; in the latter case, the program need not produce a list of moves.
A regular chessboard is a chessboard having sixteen pieces in their initial positions described in the Laws of Chess section of the FIDE Handbook. A partially regular board is a chessboard missing at least one of the regular board's sixteen pieces or including one or more additional pieces in ranks 3-6 (consisting of empty squares in the regular board) yet otherwise regular.
Eight lines of eight characters each make up a chessboard. A hyphen (
-) represents an empty square. The last line's first character represents the regular position of white's king's rook (a1 in algebraic notation) and is always a black square; both its adjacent squares are white squares (see Figure 1).
Each kind of piece has a distinct uppercase or lowercase letter for identification (see Figure 2). No two pieces having the same letter (excepting pawns) are present in a regular board, and white and black have exactly eight pawns each.
Figure 1: regular board
rnbkqbnr pppppppp -------- -------- -------- -------- PPPPPPPP RNBKQBNR
Figure 2: piece names, counts, and letters
Piece Count White Black -------------------------------- King 1 K k Queen 1 Q q Bishop 2 B b Knight 2 N n Rook 2 R r Pawn 8 P p
The program shall output one line per move. Each move follows the format
<source> is the algebraic notation for an occupied square and
<target> is the algebraic notation for an unoccupied square. (Note: Algebraic notation is described in Appendix C to the FIDE Handbook.) For example, the program shall output
a4a5 to move the piece on square
a4 to square
The generated moves shall fully regularize the chessboard if possible. If any pieces are missing from the board, the program shall output the moves necessary to partially regularize the board and then a line containing 'M' followed by the letters of all such pieces. An 'M' line shall not be output unless there is at least one missing piece.
If any additional pieces exist on the board, the program shall either a) leave them in ranks 3-6, partially regularizing the board or b) entirely omit the list of moves from its output, even if pieces are missing. The former option (a) may not be possible in some input cases. The program shall output a line containing 'A' followed by the letters of all additional pieces after all other output (including an 'M' line if present). An 'A' line shall not be output unless there is at least one additional piece.
The program's score shall be the product of its character count and the total number of moves taken for the ten test cases in
I have posted regularizable and nonregularizable test cases on Gist. On jsFiddle, I have posted the test case generator/move checker to help you check your solution. Put the board in the first box and the move list in the second box (including neither an 'M' nor an 'A' line) and click "Make Moves" to execute the moves your program has generated. To see examples of valid output, you can run my ungolfed solution on the test cases (taking 482 moves).