Python question: the Eight puzzle

information about part I please refer to http://www.chegg.com/homework-help/questions-and-answers/part-board-class-eight-puzzle-given-start-constructor-init-self-digitstr-accepts-string-in-q20856031

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

Find the file state.py in your project folder and open it in IDLE. It contains starter code for the State class. Read over the comments accompanying the starter code.

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 

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 

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

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] 

The starter code for state.py is as follows:

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

And the boad.py code is as follows:

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