/*
* 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
#include
#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;
}