Class 39 — December 3
Introduce the 15 puzzle problem
The 15 puzzle — Needs problem solving by us — Let the fun begin
Look both ways
- 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.
initialize_globals( img )
- Initializes the global variables to appropriate values based on image
cleanup( img )
- Returns a RGB-based version of image
imgwhere the bottom right corner is replaced by a black tile
initialize_board( img )
- Initializes the board using image
img— every grid spot on the board is overlaid with the corresponding tile from
scramble_board( img )
- Assigns the tiles of
imgto random board spots
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
translate_spot_into_image_coordinate( g_spot )
- Returns the image
imgcoordinate 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
overlay( tile, g_spot )
tileonto the board at grid location
- Gets the translation of
g_spotinto a board coordinate
tileonto the board at the appropiate
get_image_tile( img, g_spot )
- Returns the tile in
imgat grid location
get_board_tile( g_spot )
- Returns the tile in the board at grid location
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.
inbounds( spot )
- Determines whether
spotis 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.
- 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
- If legal, simulates sliding leftward the tile on the board that is to the right of the black tile spot.
- If legal, simulates sliding downward the tile on the board that is above the black tile spot.
- If legal, simulates sliding upward the tile on the board that is below the black tile spot.