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]