Class 39 — December 3
Introduce the 15 puzzle problem
The 15 puzzle — Needs problem solving by us — Let the fun begin
Look both ways
Download
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.
Module functions
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 fromimg
.
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 ofg_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 locationg_spot
. The coordinate can be determined by taking into account the number of tiles to the left ofg_spot
.
Function
overlay( tile, g_spot )
- Copies
tile
onto the board at grid locationg_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 locationg_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.
© 2019 Jim Cohoon | Resources from previous semesters are available. |