Eight Puzzle Problem Sets

Eight Puzzle (Parts I and II)

100 points; pair-optional

• Parts I and II should be submitted as Problem Set 17 by 10:00 p.m. EDT on Friday, November 10, 2023

Important: Problem Sets 17-20 all start here!

Preliminaries

For the last problem sets of the semester, you will be working on the Eight Puzzle. The Eight Puzzle will be divided into four problem sets spread over two weeks.

You may work on the problem sets individually or as a pair or group-of-three. Since this is a large task, we especially encourage you to work in pairs, but please review the collaboration policies of the course before doing so.

If you have questions while working on problems, please post them on Piazza, or come to office hours, or visit the TA help hours.

Make sure to submit your work on Gradescope, following the procedures found at the end of the instructions.

Overview

As discussed in class, many problems can be framed as a search for a series of actions that take you from some initial state to some goal state. Examples include robot navigation, route finding, and map labeling. For such a problem, the state space of the problem is the collection of all states that can be reached by starting in the initial state and applying some number of actions. State-space search is the technical term given to the process of searching through the state space for a path to the goal state, and many different algorithms have been developed for that process.

These problem sets involve applying state-space search to a classic problem known as the Eight Puzzle, which we’ve discussed in class. The Eight Puzzle is a 3x3 grid containing 8 numbered tiles and one empty or blank cell. Here is one possible configuration of the tiles, with the blank cell shown shaded blue:

Tiles that are adjacent to the blank cell can move into that position in the grid, and solving the puzzle involves moving the tiles until you reach the following goal state:

In this series of problem sets, you will apply state-space search to solve any valid initial configuration of the Eight Puzzle.

Most parts of these assignments will be required – including an implementation of several classic state-space algorithms – but other parts will be left to your creativity. In particular, you will see that some initial configurations of the Eight Puzzle – ones that require a large number of moves – can be difficult to solve in a reasonable amount of time, and you will be encouraged to develop variations on the required algorithms that will reduce the time needed to find a solution!

Assignment Description

Part I: A Board class for the Eight Puzzle

For the first part of the problem, you will create an initial version of a Board class for objects that represent an Eight Puzzle board.

Your tasks

0. Begin by downloading the following zip file: eight_puzzle.zip

   Unzip this archive, and you should find a folder named eight_puzzle, and within it a number of files, including board.py. Open that file in VS Code, and put your work for this part of the assignment in that file. You should not move any of the files out of the eight_puzzle folder.

1. We have given you the start of a constructor __init__(self, digitstr) that accepts a string input digitstr and assigns preliminary values to the following three attributes:

   • tiles: a reference to a 2-D list of integers with 3 rows and 3 columns that will be used to store the contents of the board. Initially, this 2-D list is filled with zeros.

   • blank_r: an integer representing the row of the blank cell; this is initially set to -1

   • blank_c: an integer representing the column of the blank cell; this is also initially set to -1

   The input digitstr is a 9-character string of digits that specifies the desired configuration of the tiles. For example, consider the following puzzle:

   

   It would be represented by the string '142358607'. Notice that:

   • the first 3 characters in the string (142) specify the contents of the first row
   • the next 3 characters (358) specify the contents of the second row
   • the final 3 characters (607) specify the contents of the last row, with 0 representing the blank cell.

   Leaving our starter code alone, add code below it that updates the values of the three Board attributes to reflect the input digitstr. For the string 142358607 described above, you should end up with the following values:

   • tiles should be [[1, 4, 2], [3, 5, 8], [6, 0, 7]]
   • blank_r should be 2, since the blank cell is in row 2
   • blank_c should be 1, since the blank cell is in column 1

   There are multiple options for processing the input digitstr, but you should use at least one loop. Here are some hints:

   • The tile at row r, column c gets its value from the digit at position (3*r + c) of the input string digitstr. For example, the tile at row 1, column 2 in the above puzzle is an 8, and that corresponds to digitstr[3*1 + 2] (i.e., position 5 in the string '142358607').

   • You can use the int() function to convert the string version of a digit to the appropriate integer.

   • Don’t forget to record the row and column numbers of the blank cell in the attributes blank_r and blank_c.

   Examples:

   >>> b = Board('142358607')
   >>> b.tiles
   [[1, 4, 2], [3, 5, 8], [6, 0, 7]]
   >>> b.blank_r
   2
   >>> b.blank_c
   1
   >>> b2 = Board('631074852')
   >>> b2.tiles
   [[6, 3, 1], [0, 7, 4], [8, 5, 2]]
   >>> b2.blank_r
   1
   >>> b2.blank_c
   0
   

2. Write a method __repr__(self) that returns a string representation of a Board object.

   In the string that __repr__ constructs, each numeric tile should be represented by the appropriate single-character string, followed by a single space. The blank cell should be represented by an underscore character ('_') followed by a space; make sure that you do not accidentally use a hyphen ('-'). There should be a newline character ('\n') after the characters for each row, so that each row will appear on a separate line when you evaluate or print a Board object. For example:

   >>> b = Board('142358607')
   >>> b
   1 4 2 
   3 5 8 
   6 _ 7
   
   >>> str(b)
   '1 4 2 \n3 5 8 \n6 _ 7 \n'
   

   Note that calling str(b) from the Shell allows us to see the full string returned by __repr__, including all of the spaces and newline characters. Make sure that your results for this call match ours.

   Hints:

   • This __repr__ will be similar to the one that you wrote for the Board class in Connect Four. You may want to use that method as a model, and to consult the hints that we gave you for that problem.

   • Remember that the __repr__ method needs to return a string, and that it should not do any printing.

   • You can use the str() function to convert an integer to a string.

   • Make sure that your __repr__ doesn’t change the object in any way. In particular, the tiles list should not change:

     >>> b = Board('142358607')
     >>> b.tiles
     [[1, 4, 2], [3, 5, 8], [6, 0, 7]]
     >>> b
     1 4 2 
     3 5 8 
     6 _ 7
     
     >>> b.tiles
     [[1, 4, 2], [3, 5, 8], [6, 0, 7]]
     

3. As discussed in class, we can simplify things by imagining that all Eight-Puzzle moves involve “moving” the blank cell. For example, in the puzzle below

   

   moving the blank up is equivalent to moving the 5 down, which produces the following board:

   

   Write a method move_blank(self, direction) that takes as input a string direction that specifies the direction in which the blank should move, and that attempts to modify the contents of the called Board object accordingly. Not all moves are possible on a given Board; for example, it isn’t possible to move the blank down if it is already in the bottom row. The method should return True or False to indicate whether the requested move was possible.

   Notes/hints:

   • The input direction can have one of the following four values: 'up', 'down', 'left', 'right'. If any other value is passed in for ‘direction’, the method should print an error message and return False without making any changes to the object.

   • Here is one possible approach to this method:

     • Start by determining the new row and column coordinates of the blank cell, based on the value of direction. At first, you should store these new coordinates in temporary local variables, not in the attributes themselves.

     • Check to see if either of the new coordinates would take you off of the board. If so, simply return False.

     • Otherwise, make the necessary changes to the Board object’s attributes and return True. Draw some pictures to help you figure out the appropriate changes. We recommend changing the necessary elements of self.tiles before changing self.blank_r or self.blank_c.

   Examples:

   >>> b = Board('142358607')
   >>> b
   1 4 2 
   3 5 8 
   6 _ 7
   
   >>> b.move_blank('up')
   True
   >>> b
   1 4 2 
   3 _ 8 
   6 5 7
   
   >>> b.tiles      # tiles should still contain only integers
   [[1, 4, 2], [3, 0, 8], [6, 5, 7]]
   >>> b.blank_r
   1
   >>> b.blank_c
   1  
   >>> b.move_blank('left')
   True
   >>> b
   1 4 2 
   _ 3 8 
   6 5 7
   
   >>> b.blank_r
   1
   >>> b.blank_c
   0  
   >>> b.move_blank('left')   # can't go any further left
   False
   >>> b                      # b is unchanged
   1 4 2 
   _ 3 8 
   6 5 7
   
   >>> b.move_blank('down')
   True
   >>> b
   1 4 2 
   6 3 8 
   _ 5 7
   
   >>> b.move_blank('right')
   True
   >>> b
   1 4 2 
   6 3 8 
   5 _ 7
   
   >>> b.move_blank('RIGHT')
   unknown direction: RIGHT
   False
   >>> b                      # b is unchanged
   1 4 2 
   6 3 8 
   5 _ 7
   
   >>> b.blank_r
   2
   >>> b.blank_c
   1
   

4. Write a method digit_string(self) that creates and returns a string of digits that corresponds to the current contents of the called Board object’s tiles attribute. For example:

   >>> b = Board('142358607')
   >>> b.digit_string()
   '142358607'
   

   Note that this call to digit_string() returns the string of digits that was used when creating the Board. However, this won’t always be the case, because the string returned by digit_string() should reflect any changes that have been made to the tiles. For example, consider this continuation of the above example:

   >>> b.move_blank('right')
   True
   >>> b.move_blank('up')
   True
   >>> b.digit_string()
   '142350678'
   

5. Write a method copy(self) that returns a newly-constructed Board object that is a deep copy of the called object (i.e., of the object represented by self).

   This method should use the Board constructor to create a new Board object with the same configuration of tiles as self, and it should return the newly created Board object.

   Hint: The Board constructor takes a string of digits. How could you easily obtain the appropriate string of digits for the called Board?

   Examples:

   >>> b = Board('142358607')
   >>> b
   1 4 2 
   3 5 8 
   6 _ 7
   
   >>> b2 = b.copy()
   >>> b2
   1 4 2 
   3 5 8 
   6 _ 7
   
   >>> b2.move_blank('up')
   True
   >>> b2
   1 4 2 
   3 _ 8 
   6 5 7
   
   >>> b    # the original Board is unchanged
   1 4 2 
   3 5 8 
   6 _ 7
   

6. Write a method num_misplaced(self) that counts and returns the number of tiles in the called Board object that are not where they should be in the goal state. You should not include the blank cell in this count, even if it’s not where it should be in the goal state. For example:

   >>> b = Board('142358607')
   >>> b
   1 4 2 
   3 5 8 
   6 _ 7 
   >>> b.num_misplaced()       # 1,4,5,7,8 tiles are out of place
   5
   >>> b.move_blank('right')   # move 7 tile where it belongs
   True
   >>> b   
   1 4 2 
   3 5 8 
   6 7 _ 
   >>> b.num_misplaced()       # 1,4,5,8 tiles are still out of place
   4
   

7. Finally, write a method __eq__(self, other) that overloads the == operator – creating a version of the operator that works for Board objects. The method should return True if the called object (self) and the argument (other) have the same values for the tiles attribute, and False otherwise.

   This method should be straightforward to implement because you can simply use the == operator to compare self.tiles and other.tiles. You do not need to explicitly compare the individual tiles yourself, because the == operator already compares the individual elements of 2-D lists.

   Examples:

   >>> b1 = Board('012345678')
   >>> b2 = Board('012345678')
   >>> b1 == b2
   True
   >>> b2.move_blank('right')
   True
   >>> b1 == b2
   False
   

Part II: A State class

For the second part of the Eight Puzzle, you will create a preliminary State class for objects that represent one of the states in a state-space search tree for the Eight Puzzle. We discussed State objects and their connection to the search tree in class.

Your tasks

0. Find the file state.py in your eight_puzzle folder and open it in VS Code. It contains starter code for the State class. Read over the comments accompanying the starter code.

1. Write a constructor __init__(self, board, predecessor, move) that constructs a new State object by initializing the following four attributes:

   • an attribute board that stores a reference to the Board object associated with this state, as specified by the parameter board

   • an attribute predecessor that stores a reference to the State object that comes before this state in the current sequence of moves, as specified by the parameter predecessor

   • an attribute move that stores a string representing the move that was needed to transition from the predecessor state to this state, as specified by the parameter move

   • an attribute num_moves that stores an integer representing the number of moves that were needed to get from the initial state (the state at the root of the tree) to this state. If predecessor is None–which means that this new state is the initial state–then num_moves should be initialized to 0. Otherwise, it should be assigned a value that is one more that the number of moves for the predecessor state.

   Because we’ve already given you an __repr__ method for the class, you should be able to test your constructor as follows:

   >>> b1 = Board('142358607')
   >>> s1 = State(b1, None, 'init')
   >>> s1
   142358607-init-0
   >>> b2 = b1.copy()
   >>> b2.move_blank('up')
   True
   >>> s2 = State(b2, s1, 'up')    # s1 is the predecessor of s2
   >>> s2
   142308657-up-1
   

2. Write a method is_goal(self) that returns True if the called State object is a goal state, and False otherwise.

   At the top of the file, we’ve given you a 2-D list called GOAL_TILES that represents the configuration of the tiles in a goal state. You can simply use the == operator to compare the tiles attribute in the Board object associated with this state to GOAL_TILES.

   Here are some test cases:

   >>> s1 = State(Board('102345678'), None, 'init')
   >>> s1.is_goal()
   False
   >>> s2 = State(Board('012345678'), s1, 'left')
   >>> s2.is_goal()
   True
   

3. Write a method generate_successors(self) that creates and returns a list of State objects for all successor states of the called State object. We discussed the concept of successor states in class.

   At the top of the file, we’ve given you a list called MOVES that contains the names of the four possible ways in which the blank cell can be moved:

   MOVES = ['up', 'down', 'left', 'right']
   

   For each of these moves, the method should do the following:

   • Create a copy of the Board object associated with this state by using the appropriate method in that Board object.

   • Attempt to apply the move by using the appropriate method in the new Board object (i.e., the copy). Make sure that you apply the move to the copy, and not to the original.

   • If the move was successful, construct a new State object for the new Board, and add that State object to the list of successors. Otherwise, don’t create a State object for that move.

   Then, once you are done trying all possible moves, return the list of successors. Here’s some pseudocode for the full method:

   def generate_successors(self):
       successors = []
       for each move m in the list MOVES:
           b = a copy of self.board
           try applying the move m to b
           if you can apply it:
               construct a new State object for the result of the move
               add the new State object to successors
       return successors
   

   Hints:

   • Make sure to take advantage of the appropriate methods in the Board objects.

   • When constructing a new State object, you should use the variable self as the second input of the constructor, since the current state (the one represented by the called object) is the predecessor of the new state.

   Examples:

   >>> b1 = Board('142358607')
   >>> b1
   1 4 2 
   3 5 8 
   6 _ 7
   
   s1 = State(b1, None, 'init')
   >>> s1
   142358607-init-0
   >>> succ = s1.generate_successors()   
   >>> succ            # 3 successors; blank can't go down from bottom row
   [142308657-up-1, 142358067-left-1, 142358670-right-1]
   >>> s1              # s1 should be unchanged
   142358607-init-0
   >>> succ[2]                        # in succ[2], blank is in lower-right
   142358670-right-1
   >>> succ[2].generate_successors()  # blank can go up or left
   [142350678-up-2, 142358607-left-2]
   >>> succ[0]                        # in succ[0], blank is in middle
   142308657-up-1
   >>> succ[0].generate_successors()  # blank can go in all four directions
   [102348657-up-2, 142358607-down-2, 142038657-left-2, 142380657-right-2]
   

Submitting Your Work

The following instructions are for submitting board and state classes as problem set 17.

You should use Gradescope to submit the following files under Problem Set 17:

• your board.py file
• your state.py file