## Class 39 — December 3

#### Introduce the 15 puzzle problem

The 15 puzzle — Needs problem solving by us — Let the fun begin

### Discussion

• The image to be used needs to be divided into 4 x 4 equal-sized tiles with the lower-righthand corner tile missing.
• Because the image width and height are not necessarily multples of 4 in length, the right and bottoms might need to be pared.
• The sixteen tiles will be labeled using their row and columns indices:

canonical_ordering = [

``      ( 0, 0 ), ( 1, 0 ), ( 2, 0 ), ( 3, 0 ),``
``      ( 0, 1 ), ( 1, 1 ), ( 2, 1 ), ( 3, 1 ),``
``      ( 0, 2 ), ( 1, 2 ), ( 2, 2 ), ( 3, 2 ),``
``      ( 0, 3 ), ( 1, 3 ), ( 2, 3 ) ]``

• A random ordering of the grid locations is alse needed.

ordering = canonical_ordering[ : ]

random.shuffle( ordering )

random_ordering = ordering

• One data structure will be maintained
• `BOARD` — the current image of the 15 puzzle
• For every board tile there is a left, right, top, and bottom line surrounding it.

### Function `initialize_globals( img )`

• Initializes the global variables to appropriate values based on image `img`

### Function `cleanup( img )`

• Returns a RGB-based version of image `img` where the bottom right corner is replaced by a black tile

### Function `initialize_board( img )`

• Initializes the board using image `img` — every grid spot on the board is overlaid with the corresponding tile from `img`.

### Function `scramble_board( img )`

• Assigns the tiles of `img` to random board spots

### Function `translate_spot_into_board_coordinate( g_spot )`

• Returns the board coordinate of the upper-left-hand corner of the tile at grid location `g_spot`. The coordinate can be determined by taking into account the number of tiles and lines to the left of `g_spot`.

### Function `translate_spot_into_image_coordinate( g_spot )`

• Returns the image `img` coordinate of the upper-left-hand corner of the tile at grid location `g_spot`. The coordinate can be determined by taking into account the number of tiles to the left of `g_spot`.

### Function `overlay( tile, g_spot )`

• Copies `tile` onto the board at grid location `g_spot`:
• Gets the translation of `g_spot` into a board coordinate
• Pastes `tile` onto the board at the appropiate

### Function `get_image_tile( img, g_spot )`

• Returns the tile in `img` at grid location `g_spot`

### Function `get_board_tile( g_spot )`

• Returns the tile in the board at grid location `g_spot`

### Function `setup( img )`

• Initializes the global variables. Gets a cleaned-up version of `img` (that is,an image whose lower-right-hand tile area is black. Initializes the board to a canonical ordering. And, returns the cleaned-up image.

### Function `inbounds( spot )`

• Determines whether `spot` is a valid grid location for a 15 puzzle. That is the row and column values of spot are both legal — at least 0 and at most 3.

### Function `slide_left()`

• Determines the grid spot to the left of the black tile. If the spot is inbounds, simulates sliding rightward the tile at that spot onto the black tile spot. The actions taken are:
• Overlays the tile on the black tile spot
• Overlays the black tile on the freed-up spot
• The location of the black tile is updated

### Function `slide_right()`

• If legal, simulates sliding leftward the tile on the board that is to the right of the black tile spot.

### Function `slide_down()`

• If legal, simulates sliding downward the tile on the board that is above the black tile spot.

### Function `slide_up()`

• If legal, simulates sliding upward the tile on the board that is below the black tile spot.