January 1996 Programmer's Challenge

Sliding Tiles

Mail solutions to: progchallenge@mactech.com

Due Date: 10 January 1996

You have all probably seen small versions of the puzzle that is the basis for this month's Challenge: a 4-by-4 grid of interlocking tiles, with one empty tile among the 16 cells allowing the puzzle to be scrambled by sliding adjacent cells into the empty location. This month the Challenge is to write code that will unscramble a larger version of the Sliding Tiles puzzle.

The prototype for the code you should write is:

typedef Boolean /*legalMove*/ (*MoveProc)( 
                      /* Callback procedure to move tile at    */
  long tileToMoveRow, /*   these coordinates into the location */
  long tileToMoveCol  /*   of adjacent empty tile              */
);
 void SolveTiles(
  long *tiles,      /* pointer to array of tiles where         */
  long numRows,     /*   tile (row,col) is at                  */
  long numCols,     /*   *(tiles + row*numCols + col)          */
  MoveProc MakeMove /* Callback procedure to move a tile       */
);

You will be given a pointer tiles into an array of tile values, the number of rows and columns in the puzzle (numRows and numCols, respectively), and the address of a callback procedure MakeMove used to tell my test code about the moves you make to solve the puzzle. The tiles array will be initialized with the values 0..numRows*numCols-1, in an order scrambled by the calling routine. The value 0 represents the empty tile.

Your code should make a sequence of calls to MakeMove and return when the puzzle is solved. Each MakeMove call exchanges the empty tile with the indicated adjacent tile. The puzzle is solved when you have moved each tile into its proper location: moving the tile with value i into location tiles[i] (i.e., row=i/numCols and col=i%numCols).

The callback routine will be something like the code provided below:

static long gNumRows,gNumCols;    /* initialized by test code */
static long gEmptyRow,gEmptyCol;  /* initialized by test code */
static long *gTiles;              /* initialized by test code */
 #define TileValue(tiles,row,col) *(tiles+(row)*gNumCols+(col))
#define OutOfRange(val,num)  (((val)<0) || ((val)>=(num)))
 static Boolean MakeMove(long tileToMoveRow,long tileToMoveCol) 
{
  long diff;
  if (OutOfRange(tileToMoveRow,gNumRows)) return false;
  if (OutOfRange(tileToMoveCol,gNumCols)) return false;
  if (tileToMoveRow == gEmptyRow) {
    diff = tileToMoveCol - gEmptyCol;
  } else if (tileToMoveCol == gEmptyCol) {
    diff = tileToMoveRow - gEmptyRow;
  } else {
    return false;
  }
  if ((diff != -1) && (diff != 1)) return false;
  TileValue(gTiles,gEmptyRow,gEmptyCol) = 
  TileValue(gTiles,tileToMoveRow,tileToMoveCol);
  gEmptyRow = tileToMoveRow;
  gEmptyCol = tileToMoveCol;
  TileValue(gTiles,gEmptyRow,gEmptyCol) = 0;



        return true;  //this is an addition - more details
}

As an example, given the initial conditions:

long tiles[] = {1,4,0,3,5,2};
SolveTiles(tiles,2,3,MakeMove);

... you could generate the following moves:

MakeMove(1,2);
MakeMove(1,1);
MakeMove(0,1);
MakeMove(0,0);
  

... to transform the puzzle like this:

1 4 0  ==>  1 4 2  ==>  1 4 2  ==>  1 0 2  ==>  0 1 2
3 5 2       3 5 0       3 0 5       3 4 5       3 4 5
 

It turns out that half of the possible permutations of the values 0..numRows*numCols-1 are "illegal" in that they cannot be reached from the "solved" state. The calling routine will provide a legal starting state - you don't have to worry about the puzzle being unsolvable.

The number of moves you make to solve the puzzle is not an explicit criterion in determining the winner, but the winner will be determined by total execution time, including the time used by the callback routine, as we did in the Master MindReader challenge a few months back. Note that you are not permitted to optimize the callback routine - its purpose is to provide a fixed time penalty for each move your solution routine makes.

This will be a native PowerPC Challenge, scored using the Symantec 8.0.3 compiler. Good luck.

Back to the Programmer's Challenge Page