ajax ... nettuts

Lesson 1 - The Fundamental Operation

If you look at the physical version of the 15-puzzle, the most fundamental operation that we perform is “moving the tiles”.

How can you move the tiles?

The only movement possible in the puzzle is to move a tile into the hole position.




For example, the tile numbered ‘7’ can move one position to the left into the hole ‘X’.

We can also say that the hole ‘X’ moves one position to the right.


  

This is the fundamental operation of this puzzle – To move the hole ‘X’ one position up/down/left/right.

Every other operation depends on this.

We will start by coding this operation.

moveHole(direction), where direction = up/down/left/right




Exercises

1. Implement the function moveHole(direction) that moves the hole from its current position one position to the up/down/left/right
  a. Make sure to take care of the boundary conditions. A hole on the extreme left cannot be moved to its left.

2. Test this function by initializing a grid to a certain position and then invoking :
  a. moveHole(left),
  b. moveHole(right)
  c. moveHole(up)
  d. moveHole(down)

Repeatedly over and over. Verify the outputs after each operation to test whether all these operations are working in order (including the boundary conditions)

3. Write a test program testMoveHole (initialHolePosition, direction) which tests that the new position of the hole is what it is supposed to be. E.g. if the initial hole position was (2,3) and the direction = left, then testMoveHole tests that the new hole position is (2,2)

Next Step

So far, we have moved the hole one position to the left/right/up/down. What is the next logical step?

Lesson 2 - Move the hole over longer distances

The next logical step is obviously to be able to move the hole over longer distances.

Let us take a simple example to consider this.

Moving the hole from one location (1, 2) to (3, 0)

This can be done in two stages:
  1. Move the hole from (1,2) to (1,0)
  2. Move the hole from (1,0) to (3,0)



Other variations are also possible. The above is just one of the suggested variations.

The diagrams below show each step of the sequence:


  

  




How can you move a hole from ANY source position to ANY destination position ?


     


Exercises

1. Implement routine moveHoleToDest(destination), which moves the hole ‘X’ from its current position to the destination position following the design given above.
2. Test this routine for various inputs
  a. Note, since the underlying routine moveHole(direction) is already tested, testing this routine will be much easier.

Next Step

So far we have looked at moving the “hole”. Now, let us get into moving the tiles.

Lesson 3 - Moving the tile numbered ‘1’ one step

Now we take the next step forward – exploring how to move the tile numbered ‘1’. We will now look at moving the tile numbered ‘1’ from its original position


Let us try to move the tile ‘1’ one position up
This can be done in two steps:
    1. Move the hole ‘X’ to the coordinate (1,1)

     

    2. Move ‘1’ one position up by swapping with ‘X’.





Moving the tile ‘1’ up is the same as saying move the hole position down




Make sure you understand the last step really well. Moving the TILE ‘1’ UPWARDS INTO THE HOLE is the same as moving the HOLE DOWNWARDS INTO THE TILE ‘1’.
This gives the final location.




Hence, we see that moving a tile one position up can be written entirely in terms of moving the hole ‘X’ :

To move the tile ‘1’ from the coordinates (tx, ty) one position up:
  • Move the hole from its current location to the location (tx – 1, ty)
  • Move the hole down to (tx, ty). This will move the tile ‘1’ one position up.



A similar logic will be used to move the tile down/left/rght.


Exercise:

1. Write the routines for moving the tile up/down/left/right.
  a. Add boundary conditions. E.g. cant move a tile in the leftmost col.
2. Test the routine by giving an initial configuration, and then repeatedly calling these functions and ensuring all boundary conditions are handled well.
  a. moveTile1(up)
  b. moveTile1(down)
  c. moveTile1(left)
  d. moveTile1(right)
3. For practice, generalize the above routine to handle any tile-number. The tile-number will be passed as a parameter. moveTile (tileNumber, direction).

Next Step
Now that we have figured out to move the tile numbered ‘1’ one step, we will figure out how to move it to the top-level position

Lesson 4 - Moving the tile numbered ‘1’ to the top-left position




Move the tile numbered ‘1’ to the extreme left and then to the top.






Exercises

  1. Implement the function moveTile1ToTopLeftPosition
  2. Test the function moveTile1ToTopLeftPosition by providing different initial inputs.
  3. Write a generealized function moveTile1ToTopLeftPosition(tileNumber) to move any tile-number to origin. (For practice)
  4. Write a generalized function moveTileToDest(tileNumber, dest) to move any tile-number to any destination indicated. (For practice)