Set the chessboard

Question

Objective

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.

Input format

Description

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

Output format

The program shall output one line per move. Each move follows the format <source><target>, where <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 a5.

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.

Score

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 regboards.txt.

Test cases

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).

Answer 1

Python, score 150552 = 306 moves * 492 chars

import os,re
B=os.read(0,99)
R='rnbkqbnr-'+8*'p'+37*'-'+8*'P'+'-RNBKQBNR'
def P(x,y):print'%c%d%c%d'%(97+x%9,8-x/9,97+y%9,8-y/9)
F={}
M=''
t=B.find('-',18,56)
for x in range(71):
 if R[x]>'@':
  if R[x]==B[x]:B=B[:x]+'-'+B[x+1:]
  else:
   y=B.find(R[x])
   if y<0:M+=R[x]
   else:F[x]=y;B=B[:y]+'-'+B[y+1:]
A=re.sub(r'[-\n]','',B)
if M:print'M',M
if A:print'A',A
else:
 while F:
  p=[x for x in F if x not in F.values()]
  if p:x=p[0];y=F[x];P(y,x);del F[x]
  else:x=min(F);P(F[x],t);F[x]=t

The code records a list of moves F which will regularize the board. This list is made by choosing a piece from the input board B to go to each location of the final board R, and 'crossing it off' of the input board. Any missing or additional pieces are computed as a side effect of this computation. Then the moves from F are made, using the temporary location t to break any cycles.