/* 
 * Solution: Missing Piece 2001
 *
 * This solution uses a modified breadth-first search.  A breadth-first
 * algorithm is ideal since it eliminates the possibility of testing
 * solutions longer than the number of moves specified.  Of course,
 * it takes more memory to store the state information required for
 * a breadth-first search than for a depth-first search, so it is
 * important to try and "trim" the portions of the solution space
 * explored to prevent running out of memory.  A quick and dirty
 * worst-case breadth-first search of the solution space would require
 * tracking around 4^15 entries, and even at just 1 byte per entry
 * that requires 1 GB of memory.
 *
 * To trim the search space, we didn't consider the following moves:
 *
 *    1) Moving the same piece twice in a row. Since this returns
 *       you to a board configuration that you had achieved two moves
 *       ago, it cannot be a member of the shortest sequence of moves
 *
 *    2) Any move that results in a board that cannot be transformed
 *       into the target board using the remaining moves.  To aid in
 *       this, we employed a quick calculation that gives us a
 *       lower bound on the number of moves it takes to get from
 *       one configuration to another.
 *
 *       This lower bound, the "Manhattan Distance", is calculated
 *       by determining how far each piece on the target board is
 *       displaced from its position on the starting board and then
 *       summing all these distances.  Each distance is calculated by
 *       determining the smallest number of vertical and horizontal
 *       moves necessary to move a piece from target to destination if
 *       the rest of the board were empty.  This represents a best
 *       case for this piece, and summing the best cases for all the
 *       pieces results in a best case (lower bound) for the board as
 *       a whole.
 *
 *       Of course, calculating the Manhattan Distance separating two
 *       boards is time consuming, so we only perform the entire
 *       calculation for the starting and target boards.  For each
 *       move, we calculate how the move affects the result.  Only
 *       one piece may move at a time, and it must move either
 *       nearer to or further from its target position.  One must
 *       simply determine which case the move represents and apply the
 *       appropriate modifier to the previous board's Manhattan 
 *       Distance to get the value for the new board.
 *
 *  One interesting side effect of using the Manhattan Distance in
 *  this way is that it eliminates the need to check whether or not
 *  the current board matches the target to find a path that worked.
 *  When the Manhattan Distance for board reaches 0, it is assured to
 *  match the target exactly.
 *
 */
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

/* Here is the node that tracks intermediate boards */
typedef struct QueueNode {
   short Depth;         /* Search depth of this board    */
   short MDist;         /* Manhattan Distance to target  */
   short LastMove;      /* ID of piece last moved        */
   short MissingRow;    /* Row of missing piece          */
   short MissingCol;    /* Col of missing piece          */
   short Board[10][10]; /* Board for this node           */
   struct QueueNode *Next;         /* Pointer to next node in queue */
} QueueNode_t;   

/* Prototypes */
int ManhattanDistance();
int InputIsValid();

/* Global Variables */
int TargetBoard[10][10];  /* Board we want to achieve */
int InitialBoard[10][10]; /* Board we start with      */
int varD, varN;           /* Variables D and N from the "START D N" line
                           * D is the dimension of one side of the 
                           * square board.
                           * N is the maximum number of moves to consider. */
FILE *infile, *outfile;   /* The I/O streams we will use */
QueueNode_t *QueueHead;   /* The head and tail of the queue we will use */
QueueNode_t *QueueTail;   /* to hold our intermediate results */

void main (void) {

   char buffer[100];
   int row,col,MDist;
   int SolutionFound, SearchDepth;
   int rowdelta, coldelta;
   int rownew, colnew;
   int rowtarget, coltarget;
   int MDistdelta;
   QueueNode_t *TempNode;

   /* Open the input and output files */
   infile = stdin;
   outfile = stdout;

   /* Process the input sets */
   while (1) { /* We'll break after an unsuccessful read attempt */
    
      /* Read the header for this input set */
      fscanf(infile,"%s %d %d",buffer,&varD,&varN);
      if (feof(infile)) break;
      if (strcmp(buffer,"START")!=0 || 
          varD < 3 || varD > 10 ||
          varN < 0 || varN > 15) {
         fprintf(stderr,"Problem with start line: \"%s %d %d\"",buffer,varD,varN);
         exit(1);
      }

      /* Read in the Initial Board */
      for (row=0; row < varD; row++) {
         for (col=0; col < varD; col++) {
            fscanf(infile,"%s",buffer);
            if (buffer[0]=='X') {
               InitialBoard[row][col]=0;
            }
            else {
               sscanf(buffer,"%d",&InitialBoard[row][col]);
            }
         }
      }

      /* Read in the Target Board */
      for (row=0; row < varD; row++) {
         for (col=0; col < varD; col++) {
            fscanf(infile,"%s",buffer);
            if (buffer[0]=='X') {
               TargetBoard[row][col]=0;
            }
            else {
               sscanf(buffer,"%d",&TargetBoard[row][col]);
            }
         }
      }

      /* Read the footer for this input set */         
      fscanf(infile," %s ",buffer);
      if (strcmp(buffer,"END")!=0) {
         fprintf(stderr,"\"%s\" != \"END\"",buffer);
         exit(1);
      }

      /* Validate the input set */
      if (!InputIsValid()) {
         fprintf(stderr,"Input set invalid! Start line = \"START %d %d\"",varD,varN);
         exit(1);
      }

      /* Initialize variables */
      SolutionFound = FALSE;
      SearchDepth = 1;
      QueueHead = NULL;
      QueueTail = NULL;

      /* Calculate a quick lower bound (Manhattan Distance) */
      MDist = ManhattanDistance();

      /* Only do a search for the solution if the Manhattan Distance
       * is less than or equal to the limiting number of moves */
      if (MDist <= varN) {

         /* Check the special case where MDist is 0 */
         if (MDist == 0) {
            SearchDepth = 0;
            SolutionFound = TRUE;
         } 
         else { /* Otherwise, seed the search queue */
            QueueHead = (QueueNode_t *) malloc(sizeof(QueueNode_t));
            QueueTail = QueueHead;
            QueueHead->Depth = 0;
            QueueHead->MDist = MDist;
            QueueHead->LastMove = 0;
            QueueHead->Next = NULL;
            for (row=0; row < varD; row++) {
               for (col=0; col < varD; col++) {
                  QueueHead->Board[row][col]=InitialBoard[row][col];
                  if (QueueHead->Board[row][col] == 0) {
                     QueueHead->MissingRow = row;
                     QueueHead->MissingCol = col;
                  }
               }
            }
         }

         /* Set the depth of the current search. */
         if (!SolutionFound) SearchDepth = QueueHead->Depth+1;

         /* Do a breadth-first search for a solution */
         while (!SolutionFound && SearchDepth <= varN) {

            /* For each of the possible moves, queue a new board */
            for (rowdelta=-1; rowdelta <= 1; rowdelta++) {
               for (coldelta=-1; coldelta <= 1; coldelta++) {

                  /* This move is only legal if we moved exactly one
                   * row OR one column, but not both */
                  if ((abs(rowdelta) - abs(coldelta)) == 0) continue;
                  rownew = QueueHead->MissingRow+rowdelta;
                  colnew = QueueHead->MissingCol+coldelta;

                  /* Don't go off the board */
                  if (rownew < 0 || colnew < 0 || 
                      rownew >= varD || colnew >= varD) 
                     continue;

                  /* Don't backtrack */
                  if (QueueHead->Board[rownew][colnew] ==
                      QueueHead->LastMove)
                     continue;

                  /* Calc the new MDist by first finding the target
                   * tile's row and column */
                  for (row=0; (row < varD); row++) {
                     for (col=0; (col < varD); col++) {
                        if (TargetBoard[row][col] == 
                            QueueHead->Board[rownew][colnew]) {
                           rowtarget=row;
                           coltarget=col;
                        }
                     }
                  }
                  
                  /* If we will move toward the target, MDist
                   * decreases, otherwise it increases */
                  if (rowdelta != 0) { /* It was a row move */
                     if (abs(abs(rowtarget) - abs(rownew-rowdelta)) >
                         abs(abs(rowtarget) - abs(rownew))) {
                        MDistdelta=1;
                     }
                     else {
                        MDistdelta=-1;
                     }
                  }
                  else  { /* It was a column move */
                     if (abs(abs(coltarget) - abs(colnew-coldelta)) >
                         abs(abs(coltarget) - abs(colnew))) {
                        MDistdelta=1;
                     }
                     else {
                        MDistdelta=-1;
                     }
                  }

                  /* If MDist is 0 we're done */
                  if ((QueueHead->MDist + MDistdelta) == 0) {
                     SolutionFound = TRUE;
                     break;
                  }

                  /* If the new MDist eliminates the new board from
                   * being a candidate, skip it */
                  if ((QueueHead->MDist + MDistdelta) > 
                      (varN - SearchDepth)) 
                     continue;

                  /* Otherwise queue this new node */
                  TempNode = (QueueNode_t *) malloc(sizeof(QueueNode_t));
                  TempNode->Depth = SearchDepth;
                  TempNode->MDist = QueueHead->MDist + MDistdelta;
                  TempNode->LastMove = QueueHead->Board[rownew][colnew];
                  TempNode->Next = NULL;
                  for (row=0; row < varD; row++) {
                     for (col=0; col < varD; col++) {
                        if (QueueHead->Board[row][col] == 0) {
                           /* Replace the missing piece with the
                            * piece moved */
                           TempNode->Board[row][col] = TempNode->LastMove;
                        }
                        else if (QueueHead->Board[row][col] == 
                                 TempNode->LastMove) {
                           /* Replace the piece moved with the
                            * mising piece */
                           TempNode->Board[row][col] = 0;
                           TempNode->MissingRow=row;
                           TempNode->MissingCol=col;
                        }
                        else {
                           TempNode->Board[row][col]=QueueHead->Board[row][col];
                        }
                     }
                  }
                  QueueTail->Next = TempNode;
                  QueueTail = TempNode;
                  TempNode = NULL;
               }
               if (SolutionFound == TRUE) break;
            } /* for (each type of move ) */
            if (SolutionFound == TRUE) break;

            /* Remove the head from the queue */
            /* If it's the last entry, we're done */
            if (QueueHead == QueueTail) {
               free(QueueHead);
               QueueHead = QueueTail = NULL;
               if (!SolutionFound)
                  SearchDepth = varN+1; /* This will kill the
                                         * while loop */
            }
            else {
               TempNode = QueueHead;
               QueueHead = TempNode->Next;
               free(TempNode);
            }

            /* Set the search depth to the depth of the current node +1 */
            if (QueueHead != NULL) SearchDepth = QueueHead->Depth+1;

         } /* while we're still looking for a solution */

         /* Free the queue nodes */
         while (QueueHead != NULL) {
            TempNode = QueueHead;
            QueueHead = TempNode->Next;
            free(TempNode);
         }

      } /* if (the MDist didn't limit us) */

      /* Print the solution for this input set */
      if (SolutionFound) {
         /* Display the solution as per the problem description */
         fprintf(outfile,"SOLVABLE WITHIN %d MOVES\n\n",SearchDepth);
      }
      else {
         /* Display the "not solvable" message */
         fprintf(outfile,"NOT SOLVABLE WITHIN %d MOVES\n\n",varN);
      }

   }

   /* Clean up */
   fclose(infile);
   fclose(outfile);

}

/* ManhattanDistance()
 * 
 * This routine will calculate a quick lower bound for the number of
 * moves necessary to get from the InitialBoard to the TargetBoard.
 */
#define ROW 0
#define COL 1

int ManhattanDistance() {
   
   int Coordinate[2][100]; /* This is a lookup table that will be
                            * populated from the Initial Board.
                            * Coordinate[ROW][Piece#] and
                            * Coordinate[COL][Piece#] are the row
                            * and column of the given piece # from
                            * the Initial Board. */
   int Distance = 0; /* This will accumulate the Manhattan Distance */
   int row, col;
   
   /* Process the Inital Board */
   for (row=0; row < varD; row++) {
      for (col=0; col < varD; col++) {
         /* Skip the missing piece */
         if (InitialBoard[row][col] != 0) {
            Coordinate[ROW][InitialBoard[row][col]]=row;
            Coordinate[COL][InitialBoard[row][col]]=col;
         }
      }
   }

   /* Review the Target Board */
   for (row=0; row < varD; row++) {
      for (col=0; col < varD; col++) {
         /* Skip the missing piece */
         if (TargetBoard[row][col] != 0) {
            /* Increment the Manhattan Distance by the minimum number
             * of moves this piece is displaced */
            Distance += 
                  abs(row - Coordinate[ROW][TargetBoard[row][col]]) +
                  abs(col - Coordinate[COL][TargetBoard[row][col]]);
         }
      }
   }
   
   /* Return the Manhattan Distance */
   return Distance;

}

/* InputIsValid()
 *
 * This routine will ensure that the input conforms to the
 * problem statement.
 *
 * A contest solution would not include a function like this since
 * contestants can assume that the data sets are valid.
 */
int InputIsValid() {

   int i, row, col;
   int found[100];

   /* Initialize the checklist */
   for (i=0; i < varD*varD; i++) found[i]=FALSE;   

   /* Check the Initial Board */
   for (row=0; row < varD; row++) {
      for (col=0; col < varD; col++) {
         if (InitialBoard[row][col] >= varD*varD ||
             InitialBoard[row][col] < 0) {
            fprintf(stderr,"Invalid square number: %d", InitialBoard[row][col]);
            return FALSE;
         }
         if (found[InitialBoard[row][col]] == TRUE) {
            fprintf(stderr,"Duplicate square number: %d", InitialBoard[row][col]);
            return FALSE;
         }
         found[InitialBoard[row][col]] = TRUE;
      }
   }

   /* Initialize the checklist */
   for (i=0; i < varD*varD; i++) found[i]=FALSE;   

   /* Check the Target Board */
   for (row=0; row < varD; row++) {
      for (col=0; col < varD; col++) {
         if (TargetBoard[row][col] >= varD*varD ||
             TargetBoard[row][col] < 0) {
            fprintf(stderr,"Invalid square number: %d", TargetBoard[row][col]);
            return FALSE;
         }
         if (found[TargetBoard[row][col]] == TRUE) {
            fprintf(stderr,"Duplicate square number: %d", TargetBoard[row][col]);
            return FALSE;
         }
         found[TargetBoard[row][col]] = TRUE;
      }
   }

   /* If we made it this far, all the tests passed */

   return TRUE;

}