Eight Puzzle Problem Sets

Eight Puzzle (Parts III)

100 points; pair-optional

• Part III should be submitted as Problem Set 18 by 10:00 p.m. EDT on Saturday, November 11, 2023

Important: This assignment builds on PS17

Part III: A Searcher class for random search

In the next part of the eight puzzle, 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 eight_puzzle folder and open it in VS Code. 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.

   We gave you pseudocode for this method in class.

   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.

   Find the file eight_puzzle.py in your eight_puzzle folder and open it in VS Code. 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 Gradescope to submit the following files under PS18:

• your searcher.py file
• your updated state.py file

If you are unable to submit and it is close to the deadline, email your homework before the deadline to your instructor. This provision only applies to problems accessing Gradescope and not to errors in your code.