Question & Answer: Part I and Part II are here: https://www.chegg.com/homework-help/questions-and-answers/python-question-eight-puzzle-information-part-please-…..

Python question: eight puzzle

Part I and Part II are here: https://www.chegg.com/homework-help/questions-and-answers/python-question-eight-puzzle-information-part-please-refer-http-wwwcheggcom-homework-help–q23444366

Answers to part I and part II are:

class Board:
“”” A class for objects that represent an Eight Puzzle board.
“””
def __init__(self, digitstr):
“”” a constructor for a Board object whose configuration
is specified by the input digitstr
input: digitstr is a permutation of the digits 0-9
“””
# check that digitstr is 9-character string
# containing all digits from 0-9
assert(len(digitstr) == 9)
for x in range(9):
assert(str(x) in digitstr)

self.tiles = [[0] * 3 for x in range(3)]
self.blank_r = -1
self.blank_c = -1

# Put your code for the rest of __init__ below.
# Do *NOT* remove our code above.
for r in range(0,3):
for c in range(0,3):
self.tiles[r][c]=int(digitstr[3*r+c])
if(self.tiles[r][c]==0):
self.blank_r=r
self.blank_c=c
### Add your other method definitions below. ###
def __repr__(self):
“””returns a string representation of a Board object
“””
s=””
for r in range(0,3):
for c in range(0,3):
if (self.tiles[r][c] is not 0):
s=s+str(self.tiles[r][c])+””
else:
s=s+”_”
s=s+”n”
return s
def move_blank(self,direction):
“””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.
“””
nr=0
nc=0
if(direction==’up’):

nr=self.blank_r-1
nc=self.blank_c

if(nr<0 or nr>2):
return False

elif(direction==’down’):
nr=self.blank_r+1
nc=self.blank_c

if(nr<0 or nr>2):
return False
elif(direction==’left’):
nr=self.blank_r
nc=self.blank_c-1

if(nc<0 or nc>2):
return False
elif(direction==’right’):
nr=self.blank_r
nc=self.blank_c+1

if(nc<0 or nc>2):
return False
else:
print(“invalid direction”)
return False

self.tiles[self.blank_r][self.blank_c]=self.tiles[nr][nc]
self.tiles[nr][nc]=0
self.blank_c=nc
self.blank_r=nr
def digit_string(self):
“””creates and returns a string of digits that corresponds
to the current contents of the called Board object’s
tiles attribute
“””
s=”
for row in range(len(self.tiles)):
for col in range(len(self.tiles[row])):
s+=str(self.tiles[row][col])
return s
def copy(self):
“””returns a newly-constructed Board object that is a deep
copy of the called object
“””
new_board=Board(self.digit_string())
return new_board
def num_misplaced(self):
“””counts and returns the number of tiles in the called Board
object that are not where they should be in the goal state
“””
count = 0
now = self.digit_string()
goal = ‘012345678’
for x in range(8):
if now[x] == 0 or now[x] == goal[x]:
count += 0
else:
count += 1
return count
def __eq__(self, other):
“”” overloads the == operator – creating a version of the
operator that works for Board objects. return True if
the called object (self) and the
argument (other) have the same
values for the tiles attribute and False otherwise.
“””
if self.digit_string() == other.digit_string():
return True
else:
return False

Part II:

from board import *

# a 2-D list that corresponds to the tiles in the goal state
GOAL_TILES = [[0, 1, 2],
[3, 4, 5],
[6, 7, 8]]

# the list of possible moves, each of which corresponds to
# moving the blank cell in the specified direction
MOVES = [‘up’, ‘down’, ‘left’, ‘right’]

class State:
“”” A class for objects that represent a state in the state-space
search tree of an Eight Puzzle.
“””
### Add your method definitions here. ###
def __init__(self,board,predecessor,move):
self.board=board
self.predecessor=predecessor
self.move=move
if predecessor == None:
self.num_moves=0
else:
self.num_moves = predecessor.num_moves+1
def is_goal(self):
return self.board.tiles == GOAL_TILES
def generate_successors(self):
successors = []
for m in MOVES:
b=self.board.copy()
if b.move_blank(m) != False:
s=State(b,self,m)
successors.append(s)
return successors

def __repr__(self):
“”” returns a string representation of the State object
referred to by self.
“””
# You should *NOT* change this method.
s = self.board.digit_string() + ‘-‘
s += self.move + ‘-‘
s += str(self.num_moves)
return s

def creates_cycle(self):
“”” returns True if this State object (the one referred to
by self) would create a cycle in the current sequence of moves,
and False otherwise.
“””
# You should *NOT* change this method.
state = self.predecessor
while state != None:
if state.board == self.board:
return True
state = state.predecessor
return False

def __gt__(self, other):
“”” implements a > operator for State objects
that always returns True. This will be needed to break
ties when we use max() on a list of [priority, state] pairs.
If we don’t have a > operator for State objects,
max() will fail with an error when it tries to compare
two [priority, state] pairs with the same priority.
“””
# You should *NOT* change this method.
return True

The starter code for searcher class is:

import random
from state import *

class Searcher:
“”” A class for objects that perform random state-space
search on an Eight Puzzle.
This will also be used as a superclass of classes for
other state-space search algorithms.
“””
### Add your Searcher method definitions here. ###

def __repr__(self):
“”” returns a string representation of the Searcher object
referred to by self.
“””
# You should *NOT* change this method.
s = type(self).__name__ + ‘: ‘
s += str(len(self.states)) + ‘ untested, ‘
s += str(self.num_tested) + ‘ tested, ‘
if self.depth_limit == -1:
s += ‘no depth limit’
else:
s += ‘depth limit = ‘ + str(self.depth_limit)
return s

### Add your BFSeacher and DFSearcher class definitions below. ###

def h0(state):
“”” a heuristic function that always returns 0 “””
return 0

### Add your other heuristic functions here. ###

class GreedySearcher(Searcher):
“”” A class for objects that perform an informed greedy state-space
search on an Eight Puzzle.
“””
### Add your GreedySearcher method definitions here. ###

def __repr__(self):
“”” returns a string representation of the GreedySearcher object
referred to by self.
“””
# You should *NOT* change this method.
s = type(self).__name__ + ‘: ‘
s += str(len(self.states)) + ‘ untested, ‘
s += str(self.num_tested) + ‘ tested, ‘
s += ‘heuristic ‘ + self.heuristic.__name__
return s

### Add your AStarSeacher class definition below. ###

The subclass timer’s starter code is:

import time

class Timer:
“””A class whose instances store the difference between two moments in time.
To time something, an instance’s start() method must be called, followed by
a call to its end() method. Each instance also has a name that is included
when the object’s __repr__() is called.
“””
def __init__(self, name=”):
self.name = name
self.start_time = None
self.end_time = None

def start(self):
self.start_time = time.time()
self.end_time = None

def end(self):
self.end_time = time.time()

def get_diff(self):
if self.start_time != None and self.end_time != None:
return abs(self.end_time – self.start_time)
else:
return None

def __repr__(self):
return ‘{}: {:.5} seconds’.format(self.name, self.get_diff())

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.

Find the file searcher.py in your project folder and open it in IDLE. 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.

Write a constructor __init__(self, depth_limit) that constructs a new Searcherobject 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

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

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 notreturn 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]

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

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.

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 on June 20th.

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

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.

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.

IMPORTANT Download this file: eight_puzzle.py to replace the version that you downloaded with the initial project.zip file. Open it in IDLE.

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.

Part IV: Subclasses for other search algorithms

In this part of the assignment you will implement other state-space search algorithms by defining classes for new types of searcher objects.

Uninformed state-space search: BFS and DFS

In searcher.py, define a class called BFSearcher for searcher objects that perform breadth-first search (BFS) instead of random search. As discussed in class, BFS involves always choosing one the untested states that has the smallest depth (i.e., the smallest number of moves from the initial state).

This class should be a subclass of the Searcher class that you implemented in Part III, and you should take full advantage of inheritance. In particular, you should not need to include any attributes in your BFSearcher class, because all of the necessary attributes will be inherited from Searcher.

Similarly, you should not need to define many methods, because most of necessary functionality is already provided in the methods that are inherited from Searcher.

However, you will need to do the following:

Make sure that your class header specifies that BFSearcher inherits from Searcher.

Because all of the attributes of a BFSearcher are inherited from Searcher, you will notneed to define a constructor for this class. Rather, we can just use the constructor that is inherited from Searcher.

Write a method next_state(self) that overrides (i.e., replaces) the next_statemethod that is inherited from Searcher. Rather than choosing at random from the list of untested states, this version of next_state should follow FIFO (first-in first-out) ordering – choosing the state that has been in the list the longest. In class, we discussed why this leads to breadth-first search. As with the original version of next_state, this version should remove the chosen state from the list of untested states before returning it.

Examples:

>>> b = Board('142358607')       
>>> s = State(b, None, 'init')
>>> s
142358607-init-0
>>> bfs = BFSearcher(-1)
>>> bfs.add_state(s)
>>> bfs.next_state()     # remove the initial state
142358607-init-0
>>> succ = s.generate_successors()
>>> succ
[142308657-up-1, 142358067-left-1, 142358670-right-1]
>>> bfs.add_states(succ)
>>> bfs.next_state()
142308657-up-1
>>> bfs.next_state()
142358067-left-1

In searcher.py, define a class called DFSearcher for searcher objects that perform depth-first search (DFS) instead of random search. As discussed in class, DFS involves always choosing one the untested states that has the largest depth (i.e., the largest number of moves from the initial state).

DFS, the next state to be tested should be one of the ones that has the largest depth in the state-space search tree.

Here again, the class should be a subclass of the Searcher class, and you should take full advantage of inheritance. The necessary steps are very similar to the ones that you took for BFSearcher, but the next_state() method should follow LIFO (last-in first-out) ordering – choosing the state that was most recently added to the list.

Examples:

>>> b = Board('142358607')       
>>> s = State(b, None, 'init')
>>> s
142358607-init-0
>>> dfs = DFSearcher(-1)
>>> dfs.add_state(s)
>>> dfs.next_state()     # remove the initial state
142358607-init-0
>>> succ = s.generate_successors()
>>> succ
[142308657-up-1, 142358067-left-1, 142358670-right-1]
>>> dfs.add_states(succ)
>>> dfs.next_state()   # the last one added, not the first!
142358670-right-1
>>> dfs.next_state()
142358067-left-1

In eight_puzzle.py, there is a helper function called create_searcher that is used to create the appropriate type of searcher object. Modify this helper function so that it will be able to create objects that perform BFS and DFS. To do so, simply uncomment the lines that handle cases in which the algorithm input is ‘BFS’ or ‘DFS’. Once you do so, you should be able to use the eight_puzzle driver function to test your BFSearcher andDFSearcher classes.

Breadth-first search should quickly solve the following puzzle:

>>> eight_puzzle('142358607', 'BFS', -1)
BFS: 0.006 seconds, 56 states
Found a solution requiring 5 moves.
Show the moves (y/n)?

You may get a different time than we did, but the rest of the results should be the same. As discussed in class, BFS finds an optimal solution for eight-puzzle problems, so 5 moves is the fewest possible moves for this particular initial state.

Depth-first search, on the other hand, ends up going deep in the search tree before it finds a goal state:

>>> eight_puzzle('142358607', 'DFS', -1)
DFS: 10.85 seconds, 3100 states.
Found a solution requiring 3033 moves.
Show the moves (y/n)?

Important: In cases like this one in which the solution has an extremely large number of moves, trying to show the moves is likely to cause an error. That’s because our print_moves_to method uses recursion, and the number of recursive calls is equal to the number of moves in the solution. Each recursive call adds a new stack frame to the top of the memory stack, and we can end up overflowing the stack when we make that many recursive calls.

To get a solution from DFS with fewer moves, we can impose a depth limit by passing it in as the third argument to the eight_puzzle function. For example:

>>> eight_puzzle('142358607', 'DFS', 25)
DFS: 6.945 seconds, 52806 states
Found a solution requiring 23 moves.
Show the moves (y/n)?

Using a depth limit of 25 keeps DFS from going too far down a bad path, but the resulting solution requires 23 moves, which is still far from optimal!

Informed state-space search: Greedy and A*

In searcher.py, define a class called GreedySearcher for searcher objects that perform greedy search. As discussed in class, greedy search is an informed search algorithms that uses a heuristic function to estimate the remaining cost needed to get from a given state to the goal state (for the Eight Puzzle, this is just an estimate of how many additional moves are needed). Greedy Search uses this heuristic function to assign a priority to each state, and it selects the next state based on those priorities.

Once again, this class should be a subclass of the Searcher class that you implemented in Part III, and you should take full advantage of inheritance. However, the changes required in this class will be more substantial that the ones in BFSearcher and DFSearcher. Among other things, GreedySearcher objects will have a new attribute called heuristic that will allow you to choose among different heuristic functions, and they will also have a new method for computing the priority of a state.

Here are the necessary steps:

Make sure that your class header specifies that GreedySearcher inherits from Searcher.

Write a method priority(self, state) that takes a State object called state, and that computes and returns the priority of that state. For now, the method should compute the priority as follows:

priority = -1 * num_misplaced_tiles

where num_misplaced_tiles is the number of misplaced tiles in the Board object associated with state. Take advantage of the appropriate Board method to determine this value.

Copy the following constructor into the GreedySearcher class:

def __init__(self, heuristic, depth_limit):
    """ constructor for a GreedySearcher object
        inputs:
         * heuristic - a reference to the function that should be used 
         when computing the priority of a state
         * depth_limit - the depth limit of the searcher
    """
    self.heuristic = heuristic
    self.states = []
    self.num_tested = 0
    self.depth_limit = depth_limit

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

Two things worth noting:

GreedySearcher objects have an extra attribute called heuristic (and an associated extra input to their constructor). This attribute stores a reference to
which heuristic function the GreedySearcher should use. We’re not currently using this attribute in our priority method, but ultimately the method will use this attribute to choose between multiple different heuristic functions for estimating a State‘s remaining cost. If needed, you should review the powerpoint notes about this on Blackboard.

A GreedySearcher object’s states attribute is not just a list of states. Rather, it is a list of lists, where each sublist is a [priority, state] pair. This will allow a GreedySearcher to choose its next state based on the priorities of the states. Thus, we initialize states to be a list containing a sublist in which the initial state is paired with its priority.

Example:

>>> b = Board('142358607')       
>>> s = State(b, None, 'init')
>>> g = GreedySearcher(h1, -1)  # basic heuristic, no depth limit
>>> g.add_state(s)
>>> g.states     # sublist pairing initial state with its priority
[[-5, 142358607-init-0]]

If you don’t see a priority value of -5, check your priority method for possible problems.

Write a method add_state(self, state) that overrides (i.e., replaces) the add_state method that is inherited from Searcher. Rather than simply adding the specified state to the list of untested states, the method should add a sublist that is a [priority, state] pair, where priority is the priority of state, as determined by calling the priority method.

Examples:

>>> b = Board('142358607')       
>>> s = State(b, None, 'init')
>>> g = GreedySearcher(h1, -1)
>>> g.add_state(s)
>>> g.states
[[-5, 142358607-init-0]]
>>> succ = s.generate_successors()
>>> g.add_state(succ[0])
>>> g.states
[[-5, 142358607-init-0], [-5, 142308657-up-1]]
>>> g.add_state(succ[1])
>>> g.states
[[-5, 142358607-init-0], [-5, 142308657-up-1], [-6, 142358067-left-1]]

Write a method next_state(self) that overrides (i.e., replaces) the next_statemethod that is inherited from Searcher. This version of next_state should choose one of the states with the highest priority.

Hints:

You can use max to find the sublist with the highest priority. If multiple sublists are tied for the highest priority, max will choose one of them.

You should remove the selected sublist from states, and you should return only the state component of the sublist – not the entire sublist.

Examples:

>>> b = Board('142358607')       
>>> s = State(b, None, 'init')
>>> g = GreedySearcher(h1, -1)  # basic heuristic, no depth limit
>>> g.add_state(s)
>>> succ = s.generate_successors()
>>> g.add_state(succ[1])
>>> g.states
[[-5, 142358607-init-0], [-6, 142358067-left-1]]
>>> g.next_state()    # -5 is the higher priority
142358607-init-0
>>> g.states
[[-6, 142358067-left-1]]

In searcher.py, define a class called AStarSearcher for searcher objects that perform A* search. Like greedy search, A* is an informed search algorithm that assigns a priority to each state based on a heuristic function, and that selects the next state based on those priorities. However, when A* assigns a priority to a state, it also takes into account the cost that has already been expended to get to that state (i.e. the number of moves to that state). More specifically, the priority of a state is computed as follows:

priority = -1 * (heuristic + num_moves)

where heuristic is the value that the selected heuristic function assigns to the state, and num_moves is the number of moves that it took to get to that state from the initial state.

Once again, you should take full advantage of inheritance. However, we’re leaving it up to you decide which class to inherit from and how much new, non-inherited code is needed!

Here’s one thing you need to know: When constructing an AStarSearcher object, you will need to specify two inputs: (1) function that specifies which heuristic function should be used, and (2) an integer for the depth limit. See below for an example of constructing one.

Examples:

>>> b = Board('142358607')       
>>> s = State(b, None, 'init')
>>> a = AStarSearcher(h1, -1)  # basic heuristic, no depth limit
>>> a.add_state(s)
>>> a.states          # init state has same priority as in greedy
[[-5, 142358607-init-0]]
>>> succ = s.generate_successors()
>>> a.add_state(succ[1])
>>> a.states         # succ[1] has a priority of -1*(6 + 1) = -7
[[-5, 142358607-init-0], [-7, 142358067-left-1]]
>>> a.next_state()   # -5 is the higher priority
142358607-init-0
>>> a.states
[[-7, 142358067-left-1]]

Modify the create_searcher helper function in eight_puzzle.py so that it will be able to create GreedySearcher and AStarSearcher objects. To do so, simply uncomment the lines that handle cases in which the algorithm input is ‘Greedy’ or ‘A*’.

After you do so, try using the eight_puzzle driver function to see how the informed search algorithms perform on various puzzles. Here are some digit strings for puzzles that you might want to try, along with the number of moves in their optimal solutions:

‘142358607’ – 5 moves

‘031642785’ – 8 moves

‘341682075’ – 10 moves

‘631074852’ – 15 moves

‘763401852’ – 18 moves

‘145803627’ – 20 moves

A* should obtain optimal solutions; Greedy Search may or may not.

If a given algorithm ends up taking longer than you can afford to wait, you can stop it by using Ctrl-C from the keyboar