Final Project, part 1: The 8-Puzzle and Searching

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

For each problem in this problem set, we will be writing or evaluating some Python code. You are encouraged to use the Spyder IDE which will be discussed/presented in class, but you are welcome to use another IDE if you choose.

If you have questions while working on this assignment, please post them on Piazza! This is the best way to get a quick response from your classmates and the course staff.

If you have questions while working on this assignment, please post them on Piazza! This is the best way to get a quick response from your classmates and the course staff.

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

The project involves 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 project, you will apply state-space search to solve any valid initial configuration of the Eight Puzzle.

Some parts of the project 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!

Project Description

Part I: A Board class for the Eight Puzzle

For the first part of the project, 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: project.zip

   Unzip this archive, and you should find a folder named project, and within it a number of files, including board.py. Open that file in Spyder, and put your work for this part of the project in that file. You should not move any of the files out of the project 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 Problem Set 10. 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 project, 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 project folder and open it in Spyder. 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]
   

Part III: A Searcher class for random search

In the next part of the project, you will begin to implement the actual state-space search process. As discussed in class, we will use searcher objects to perform the search for us. Different types of searcher objects will implement different state-space search algorithms, and we’ll take advantage of inheritance when defining the searcher classes.

0. Find the file searcher.py in your project folder and open it in Spyder. It contains some starter code, including the beginnings of a class called Searcher, which will perform a random state-space search. Read over the comments accompanying the starter code.

1. Write a constructor __init__(self, depth_limit) that constructs a new Searcher object by initializing the following attributes:

   • an attribute states for the Searcher‘s list of untested states; it should be initialized to an empty list.

   • an attribute num_tested that will keep track of how many states the Searcher tests; it should be initialized to 0

   • an attribute depth_limit that specifies how deep in the state-space search tree the Searcher will go; it should be initialized to the value specified by the parameter depth_limit.
     (A depth_limit of -1 indicates that the Searcher does not use a depth limit.)

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

   >>> searcher1 = Searcher(-1)    # -1 means no depth limit
   >>> searcher1
   0 untested, 0 tested, no depth limit
   >>> searcher2 = Searcher(10)
   >>> searcher2
   0 untested, 0 tested, depth limit = 10
   

2. Write a method should_add(self, state) that takes a State object called state and returns True if the called Searcher should add state to its list of untested states, and False otherwise.

   The method should return False if either of these conditions holds:

   • the Searcher has a depth limit (i.e., its depth limit is not -1) and state is beyond the depth limit (i.e., the number of moves used to get to state is greater than the depth limit)

   • state creates a cycle in the search, because the same board already appears in the sequence of moves that led to state. We’ve given you a method in the State class called creates_cycle() that checks for this. Read the comments accompanying that method to understand how it works, and apply it appropriately here.

   If neither of these conditions holds, the method should return True.

   Examples:

   >>> b1 = Board('142358607')
   >>> s1 = State(b1, None, 'init')  # initial state
   >>> searcher1 = Searcher(-1)  # no depth limit
   >>> searcher1.add_state(s1)
   >>> searcher2 = Searcher(1)   # depth limit of 1 move!
   >>> searcher1.add_state(s1)
   >>> b2 = b1.copy()
   >>> b2.move_blank('left')
   True
   >>> s2 = State(b2, s1, 'left')    # s2's predecessor is s1
   >>> searcher1.should_add(s2)
   True
   >>> searcher2.should_add(s2)
   True
   >>> b3 = b2.copy()
   >>> b3.move_blank('right')        # get the same board as b1 
   True
   >>> s3 = State(b3, s2, 'right')   # s3's predecessor is s2
   >>> searcher1.should_add(s3)      # adding s3 would create a cycle
   False
   >>> searcher2.should_add(s3)
   False
   >>> b3.move_blank('left')         # reconfigure b3
   True
   >>> b3.move_blank('up')
   True
   >>> s3 = State(b3, s2, 'up')      # recreate s3 with new b3 (no cycle)
   >>> s3.num_moves
   2
   >>> searcher1.should_add(s3)      # searcher1 has no depth limit
   True
   >>> searcher2.should_add(s3)      # s3 is beyond searcher2's depth limit
   False
   

3. Write a method add_state(self, new_state) that adds takes a single State object called new_state and adds it to the Searcher‘s list of untested states. This method should only require one line of code! It should not return a value.

   For the sake of efficiency, we recommend that you do not do something like the following:

   self.states = self.states + ...     # don't do this!
   

   Rather, we recommend that you either use the += operator or the append method in the list object. We will discuss the reasons for this in class.

   Examples:

   >>> b = Board('142358607')
   >>> s = State(b, None, 'init')
   >>> searcher = Searcher(-1)
   >>> searcher.add_state(s)
   >>> searcher.states
   [142358607-init-0]
   >>> succ = s.generate_successors()
   >>> succ
   [142308657-up-1, 142358067-left-1, 142358670-right-1]
   >>> searcher.add_state(succ[0])  # add just the first successor
   >>> searcher.states
   [142358607-init-0, 142308657-up-1]
   

4. Write a method add_states(self, new_states) that takes a list State objects called new_states, and that processes the elements of new_states one at a time as follows:

   • If a given state s should be added to the Searcher‘s list of untested states (because s would not cause a cycle and is not beyond the Searcher‘s depth limit), the method should use the Searcher‘s add_state() method to add s to the list of states.

   • If a given state s should not be added to the Searcher object’s list of states, the method should ignore the state.

   This method should not return a value.

   Notes/hints:

   • Take advantage of the Searcher‘s method for determining if a state should be added.

   • Make sure that you use add_state() when adding the individual states to the list, rather than adding them yourself. This will will allow you to make fewer changes when you use inheritance to define other types of searchers.

   Examples:

   >>> b = Board('142358607')
   >>> s = State(b, None, 'init')
   >>> searcher = Searcher(-1)
   >>> searcher.add_state(s)
   >>> searcher.states
   [142358607-init-0]
   >>> succ = s.generate_successors()
   >>> succ
   [142308657-up-1, 142358067-left-1, 142358670-right-1]
   >>> searcher.add_states(succ)             # add all of the successors
   >>> searcher.states
   [142358607-init-0, 142308657-up-1, 142358067-left-1, 142358670-right-1]
   >>> succ[-1]
   142358670-right-1
   >>> succ2 = succ[-1].generate_successors() 
   >>> succ2
   [142350678-up-2, 142358607-left-2]
   >>> searcher.add_states(succ2)
   >>> searcher.states
   [142358607-init-0, 142308657-up-1, 142358067-left-1, 142358670-right-1, 142350678-up-2]
   

   Note that the last call to add_states above took a list of two states (the list given by succ2), but that only one of them (the state 142350678-up-2) was actually added to searcher‘s list of states. That’s because the other state (142358607-left-2) has the same board as the initial state and would thus create a cycle.

5. Copy the following method into your Searcher class:

   def next_state(self):
       """ chooses the next state to be tested from the list of 
           untested states, removing it from the list and returning it
       """
       s = random.choice(self.states)
       self.states.remove(s)
       return s
   

   Make sure to maintain the appropriate indentation when you do so.

   This method will be used to obtain the next state to be tested, and you should review it carefully. Here are two points worth noting:

   • Because Searcher objects perform a random search through the search space, we are using the random.choice method to randomly choose one of the elements of the states list.

   • We’re using a list method called remove to remove the selected state s from the states list.

6. Finally, write a method find_solution(self, init_state) that performs a full random state-space search, stopping when the goal state is found or when the Searcher runs out of untested states.

   • To begin, the method should add the parameter init_state to the list of untested states;

   • If the searcher finds a goal state, it should return it.

   • If the searcher runs out of untested states before finding a goal state, it should return the special keyword None. (Note that there should not be any quotes around None, because it is not a string.)

   • The method should increment the Searcher object’s num_tested attribute every time that it tests a state to see if it is the goal.

   Make sure that you take advantage of existing methods – both those available in the Searcher (i.e., in self) and those available in the State objects. Among other methods, you should use the Searcher object’s next_state() method to obtain the next state to be tested.

   Example 1:

   >>> b = Board('012345678')       # the goal state!
   >>> s = State(b, None, 'init')   # start at the goal
   >>> s
   012345678-init-0
   >>> searcher = Searcher(-1)
   >>> searcher
   0 untested, 0 tested, no depth limit
   >>> searcher.find_solution(s)     # returns init state, because it's a goal state
   012345678-init-0
   >>> searcher
   0 untested, 1 tested, no depth limit
   

   Example 2 (results may vary because of randomness):

   >>> b = Board('142358607')       
   >>> s = State(b, None, 'init')   
   >>> s
   142358607-init-0
   >>> searcher = Searcher(-1)
   >>> searcher
   0 untested, 0 tested, no depth limit
   >>> searcher.find_solution(s)     # returns goal state at depth 11
   012345678-up-11
   >>> searcher
   273 untested, 370 tested, no depth limit
   >>> searcher = Searcher(-1)   # a new searcher with the same init state
   >>> searcher
   0 untested, 0 tested, no depth limit
   >>> searcher.find_solution(s)     # returns goal state at depth 5
   012345678-left-5
   >>> searcher
   153 untested, 205 tested, no depth limit
   

7. In order to see the full solution (i.e., the sequence of moves from the initial state to the goal state), we need to add a method to the State class that will follow predecessor references back up the state-space search tree in order to find and print the sequence of moves.

   Open up your state.py file, and add a method print_moves_to(self) that prints the sequence of moves that lead from the initial state to the called State object (i.e., to self).

   To accomplish this task, you should first review the attributes that each State object has inside it. Consult the guidelines for the State class __init__ method as needed.

   Next, it’s worth noting that this method will be starting at a given State object and following predecessor references back to the initial state. However, we want to print the sequence of moves in the reverse order – from the initial state to the called State object. One way to do this is using recursion, as shown in the following pseudocode:

   def print_moves_to(self):
       if self is the initial state:    # base case
           print('initial state:')
           print the board associated with self
       else:
           make a recursive call to print the moves to the predecessor state
           print the move that led to self (see format below)
           print the board associated with self
   

   Because the recursive call on the predecessor state comes before the processing of self, the method will print the sequence of moves in the correct order.

   Example (results may vary because of randomness):

   >>> b = Board('142305678')    # only 2 moves from a goal
   >>> b
   1 4 2 
   3 _ 5 
   6 7 8
   
   >>> s = State(b, None, 'init')   
   >>> searcher = Searcher(-1)
   >>> goal = searcher.find_solution(s)
   >>> goal
   012345678-left-2
   >>> goal.print_moves_to()
   initial state:
   1 4 2 
   3 _ 5 
   6 7 8
   
   move the blank up:
   1 _ 2 
   3 4 5 
   6 7 8
   
   move the blank left:
   _ 1 2 
   3 4 5 
   6 7 8
   
   >>>
   

   Although the sequence of moves may vary because of randomness, the format of the output should be the same as what you see above.

8. Once you have completed all of the methods specified above, you can use the driver function that we have provided to facilitate the process of solving a given puzzle.

   You do not need to implement any code for this function. This is showing you how we can test the Searcher object to solve a puzzle

   Find the file eight_puzzle.py in your project folder and open it in Spyder. The driver function is called eight_puzzle, and it has two mandatory inputs:

   • a string describing the board configuration for the initial state

   • a string specifying the search algorithm that you want to use; for now, the only option is random.

   • param - a parameter that is used to specify either a depth limit or the name of a heuristic function; we will give it default value of -1.

   There is also a third, optional input that we will describe later.

   Here’s an example of how you would call it:

   >>> eight_puzzle('142358607', 'random', -1)
   

   After finding a solution, the function will ask if you want to see the moves. Enter y to see them, or anything else to end the function without seeing them.

   Important: After making changes to any of your Python files, you should rerun the eight_puzzle.py file before using the driver function to test your changed code.

Submitting Your Work

You should use Gradesope to submit the following files:

• your board.py file
• your state.py file
• your searcher.py file
• your eight_puzzle.py file