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 Nonewhich means that this new state is the initial statethen 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 weve 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, weve 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 Stateobjects for all successor states of the called State object. We discussed the concept of successor states in lecture.

At the top of the file, weve 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, dont create a State object for that move.

Then, once you are done trying all possible moves, return the list of successors. Heres 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] 

Here are some helpful codes.

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

for r in range(3): for c in range(3): self.tiles[r][c] = int(digitstr[r * 3 + c]) if self.tiles[r][c] == 0: self.blank_r = r self.blank_c = c

def __repr__(self): """ returns a string representation of a Board object. """ result = '' for r in range(3): for c in range(3): if self.tiles[r][c] == 0: result += '_' else: result += str(self.tiles[r][c]) result += ' ' result += ' ' return result

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 The method should return True or False to indicate whether the requested move was possible. """ row = self.blank_r col = self.blank_c if direction == 'up': row = self.blank_r - 1 elif direction == 'down': row = self.blank_r + 1 elif direction == 'left': col = self.blank_c - 1 elif direction == 'right': col = self.blank_c + 1 else: print('unknown direction: ' + str(direction)) return False if row not in range(3) or col not in range(3): return False else: new = self.tiles[row][col] self.tiles[row][col] = 0 self.tiles[self.blank_r][self.blank_c] = new self.blank_r = row self.blank_c = col return True

def digit_string(self): """ creates and returns a string of digits that corresponds to the current contents of the called Board objects tiles attribute. """ string = '' for r in range(3): for c in range(3): if self.tiles[r][c] == '_': string += '0' else: string += str(self.tiles[r][c]) return string

def copy(self): """ returns a newly-constructed Board object that is a deep copy of the called object """ copy = Board(self.digit_string()) return copy

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. """ number = 0 now = self.digit_string() goal = '012345678' for x in range(8): if now[x] == 0 or now[x] == goal[x]: number += 0 else: number += 1 return number

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

from board import *

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