Class 40 — December 5

Complete the 15 puzzle problem

The 15 puzzle — Needs problem solving today — The fun continues

---

---

Look both ways

• Back and ahead

---

Help make CS 1112 better

• Provide anonymous feedback

---

Download

• support.py

• fifteen.py

---

Task

• Implement five functions for module support.py. The module supports the initializing and updating of a 15 tile game. The functions are:

• inbounds()

• slide_left()

• slide_right()

• slide_up()

• slide_down()

Descriptions of the functions are available at the end of the module functions section.

---

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 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.

---

 

---

 

 

 
   
   
   
 

© 2019 Jim Cohoon

Resources from previous semesters are available.