// CSC444H1F Solution Code for Assignment 1 (with no input validation). // By Prof. Penny, November 8, 2006 // Release Notes: // - Added Manhattan Distance // - Sorted the moves in "solve" by closest to solution first. // - Reduced run-time to 55% of alternative. // - Tried a simpler version using only the Manhattan distance of the blank square // - Did surprisingly well (65%) but not better than global distance // - Optimized computation of distance // - Use a lookup table for individual tile distances // - Do incremental changes to distance when moving // - Move Undo // - Previous release copied board anew before each move. // - This release undoes the move. // - Reduced run-time to 95% // - Distance Optimizations // - Since keeping distances, able to perform certain operations more efficiently // - isSolved() reduced to one comparison // - isSameBoard() checks if distances are the same first. // - check for blank row,col the same still speeds things up even with above // - Asserts // - added copious assertions inspired by tutorial // - spotted some nascent defects very early on // #include <memory.h> #include <stdlib.h> #include <stdio.h> #include <malloc.h> #include <assert.h> // undefine to enable assertions #define NDEBUG const int MaxN = 99; // for input validation const int MaxDepth = 30; // Would take over 1 day to solve depth 30 int N; // Board dimension int BoardBytes; // Bytes to allocate for each board structure (below) int InfiniteDistance; // No distances are equal to or greater than this int boardDistance(struct board* b); // forward declarion for use by isValid(board) // Need to keep track of all boards in the current depth-first search // in order to both // 1. remember the sequence of moves // 2. ensure we are not loooping struct board { int move; // Index into "moveDirections" for next move for this board int distance; // Manhattan distance to solution int blankRow; // 0..N-1 int blankCol; // 0..N-1 int tiles[1]; // indexed as tiles[row*N+col] - will allocate sufficient storage for NxN } *boards[MaxDepth+1]; // Return true iff "b" is a valid board. // Ignore the stored distance if "otherThanDistance" is true. bool isValid(struct board *b, bool otherThanDistance = false ) { bool *found = (bool*)malloc(sizeof(bool)*N*N); for(int i=0; i < N*N; i++) found[i] = false; for(int row = 0; row < N; row++) for(int col = 0; col < N; col++) { int tile = b->tiles[row*N+col]; // range check tile if( tile < 0 || N*N-1 < tile ) return false; // check if already appeared if( found[tile] ) return false; found[tile] = true; // check if blank square recorded correctly if( tile==0 ) if( b->blankCol != col || b->blankRow != row ) return false; } // done if we do not check distance if( otherThanDistance ) return true; return b->distance == boardDistance(b); } // Static array of possible move directions for the blank square const int NumMoveDirections = 4; struct MoveDirection { int row; // -1,0,+1 int col; // -1,0,+1 const char *name; // user-readable name of this move int opposite; // 0-3 the move that undoes this move } moveDirections[NumMoveDirections] = { {-1,0,"up",1}, {+1,0,"down",0}, {0,-1,"left",3}, {0,+1,"right",2} }; // Stores pre-computed distances for the various tiles in the various locations. // See "tileDistance()" below for how to index this array int *tiledist; // array of integers of dimension [N*N][N][N] // Return the number of moves required to move "tile" from "row,col" // to its correct final destination. int tileDistance(int tile, int row, int col) { assert(0<=tile && tile<N*N && 0<=row && row<N && 0<=col && col<N); return tiledist[(tile*N + row)*N + col]; } // Initialize the "tiledist" array void initDistance() { tiledist = (int*)malloc(N*N*N*N*sizeof(int)); // Iterate through each tile for(int trow = 0; trow < N; trow++) for(int tcol = 0; tcol < N; tcol++) { int tile = trow*N+tcol+1; if( tile == N*N ) tile = 0; // "trow,tcol" is where "tile" is in the solution. // Iterate through each location it could be in. for(int row = 0; row < N; row++) for(int col = 0; col < N; col++) { // if row,col is where tile is, distance is as follows tiledist[ (tile*N + row)*N + col ] = abs(tcol-col) + abs(trow-row); } } // N*N tiles, max distance of each tile is N-1 in each of the 2 dimensions. InfiniteDistance = N*N * 2*(N-1) + 1; } // Return the distance of the board "b" from the solution. // Only ever used once for the initial input board. int boardDistance(struct board* b) { assert( isValid(b,true) ); int d = 0; for(int row=0; row < N; row++) for(int col=0; col < N; col++) d += tileDistance(b->tiles[row*N+col],row,col); return d; } // Return the new distance if we moved the blank in board "b" in direction "md". // Return InfiniteDistance if the move is not possible. int moveDistance(struct board* b, int md) { assert( isValid(b) && 0<=md && md<NumMoveDirections ); // Compute new blank positions and return InfiniteDistance if out of range int blankRow = b->blankRow + moveDirections[md].row; if( blankRow < 0 || blankRow >= N ) return InfiniteDistance; int blankCol = b->blankCol + moveDirections[md].col; if( blankCol < 0 || blankCol >= N ) return InfiniteDistance; // The tile that will move int tile = b->tiles[blankRow*N+blankCol]; // The new distance is the old, subtract out the two places that changed // in the old board, add in the two places that changed in the new board. // tile at blankRow,blankCol is moving to b->blankRow,b->blankCol // blank (0) at b->blankRow,b->blankCol is moving to blankRow,blankCol return b->distance - tileDistance(0,b->blankRow,b->blankCol) - tileDistance(tile,blankRow,blankCol) + tileDistance(tile,b->blankRow,b->blankCol) + tileDistance(0,blankRow,blankCol); } // Apply the move in direction "md" to the board "b". // Set distance to the previously computed "newDistance". void move(struct board* b, int md, int newDistance ) { assert( isValid(b) && 0<=md && md<NumMoveDirections && moveDistance(b,md)!=InfiniteDistance); // Compute new blank position. int blankRow = b->blankRow + moveDirections[md].row; int blankCol = b->blankCol + moveDirections[md].col; // Tile at new blank position is moving to old. b->tiles[b->blankRow*N+b->blankCol] = b->tiles[blankRow*N+blankCol]; // Record new blank position. b->blankCol = blankCol; b->blankRow = blankRow; // Move the blank tile (required for efficient isSameBoard() and easy printing). b->tiles[blankRow*N+blankCol] = 0; // Stach the new distance b->distance = newDistance; assert( isValid(b) ); } // Return if the board "b" is in the correct final position or not. bool isSolved(struct board *b) { assert( isValid(b) ); return b->distance == 0; } // Return if board "b1" is the same configuration as board "b2" or not. bool isSameBoard(struct board *b1, struct board *b2) { assert( isValid(b1) && isValid(b2) ); // Not the same if different distances. if( b1->distance != b2->distance ) return false; // Not the same if different blank square, if(b1->blankCol != b2->blankCol || b1->blankRow != b2->blankRow ) return false; // Different if any tile is different. for(int i=0; i < N*N; i++) if( b1->tiles[i] != b2->tiles[i] ) return false; // Otherwise must be the same. return true; } // Dump board "b" to stdout for debug purposes. // Indent 2*level spaces. void prBoard(int level, struct board *b) { printf("\n"); for(int row = 0; row < N; row++) { for(int i = 0; i < level*2; i++) printf(" "); for(int col = 0; col < N; col++) printf("%02d ",b->tiles[row*N+col]); if( row == N-1 ) printf(" d=%d", b->distance ); printf("\n"); } } // Attempt to solve the board at "board[curlevel]". // Do not recurse deeper than "maxlevel" in total. // Return if successful at solving the board within maxlevel moves. bool solve(int maxlevel, int curlevel) { // alias for current board struct board *curb = boards[curlevel]; assert( isValid(curb) ); // Return solved if this board represents a solution if( isSolved(curb) ) return true; // Return with no solution if at maximum depth if(curlevel == maxlevel) return false; // Return with no solution if seen this board before on this descent (a move loop) for(int n=curlevel-1; n>=0; n--) if( isSameBoard(curb,boards[n]) ) return false; // Pre-compute the distances for each possible next board. // Store the distances into "moveDistances". // Store InfiniteDistance if the move is not possible. // Keep track of the number of possible moves in "numMoves". int moveDistances[NumMoveDirections]; int numMoves = 0; for(int md = 0; md < NumMoveDirections; md++) if( (moveDistances[md]=moveDistance(curb,md)) < InfiniteDistance ) numMoves++ ; // Copy the current board into the next candidate board struct board *nextb = boards[curlevel+1]; memcpy(nextb,curb,BoardBytes); // Iterate through all possible moves while( numMoves > 0 ) { assert( isSameBoard(curb,nextb) ); // Store the move with the lowest distance into "nextMove". int nextMove; int lowestSoFar = InfiniteDistance; for(int move = 0; move < NumMoveDirections; move++) if( moveDistances[move] < lowestSoFar ) { nextMove = move; lowestSoFar = moveDistances[move]; } assert( lowestSoFar < InfiniteDistance ); assert( 0 <= nextMove && nextMove < NumMoveDirections ); // Make the move and store the pre-computed distance. move(nextb, nextMove, moveDistances[nextMove]); assert( isValid(nextb) ); // Attempt to solve this new board in one less move. if( solve(maxlevel,curlevel+1) ) { // Record which move we took and return success. curb->move = nextMove; return true; } // Record that we eliminated one move with the pre-decrement and test if not last. if( --numMoves > 0 ) { // Still more moves to try. // Ensure the last move tried is not chosen again. moveDistances[nextMove] = InfiniteDistance; // Reset the next board back to "curb" (this is faster than re-copying). move(nextb, moveDirections[nextMove].opposite, curb->distance); } } // Could not solve after all legal moves - no solution from the current board. return false; } // Driver routine. // Input the dimension of the board followed by the board. // Output the minimal move sequence. int main(int argc, char* argv[]) { // Read the size of board into "N". scanf("%d",&N); if( N <= 0 || MaxN < N ) { printf("Invalid dimension input\n"); return 1; } // Initialize the data strucure used to compute Manhattan distance to solution. initDistance(); // Allocate board "stack" storage. BoardBytes = sizeof(struct board) + sizeof(int)*(N*N-1); for(int n=0; n<=MaxDepth; n++) boards[n] = (struct board*)malloc(BoardBytes); // Input the board into "boards[0]". for(int row=0; row<N; row++) for(int col=0; col<N; col++) { scanf("%d",&(boards[0]->tiles[row*N+col])); if( boards[0]->tiles[row*N+col] == 0 ) { // this is the blank space boards[0]->blankCol = col; boards[0]->blankRow = row; } } if( !isValid(boards[0],true) ) { printf("Invalid board input\n"); return 1; } // Compute the distance of the initial board boards[0]->distance = boardDistance(boards[0]); // Depeen the search one move at a time for(int maxlevel = 0; maxlevel <= MaxDepth; maxlevel++) { assert( isValid(boards[0]) ); // Can we solve within "maxlevel" moves? if( solve(maxlevel,0) ) { // If yes, print out the move sequence that solves it printf("Solved in %d moves\n", maxlevel); for(int n=0; n<maxlevel; n++) printf("%d - %s\n", boards[n]->distance, moveDirections[boards[n]->move].name); return 0; } } // Could not find a solution printf("No solution found in %d moves.\n", MaxDepth); return 1; }