Python question: the Eight puzzle information about part I please refer to http:

Question

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 None–which means that this new state is the initial state–then 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 we’ve already given you an __repr__ method for the class, you should be able to test your constructor as follows:

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, we’ve 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:

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, we’ve given you a list called MOVES that contains the names of the four possible ways in which the blank cell can be moved:

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, don’t create a State object for that move.

Then, once you are done trying all possible moves, return the list of successors. Here’s some pseudocode for the full method:

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:

Explanation / Answer

import random import math _goal_state = [[1,2,3], [4,5,6], [7,8,0]] def index(item, seq): """Helper function that returns -1 for non-found index value of a seq""" if item in seq: return seq.index(item) else: return -1 class EightPuzzle: def __init__(self): # heuristic value self._hval = 0 # search depth of current instance self._depth = 0 # parent node in search path self._parent = None self.adj_matrix = [] for i in range(3): self.adj_matrix.append(_goal_state[i][:]) def __eq__(self, other): if self.__class__ != other.__class__: return False else: return self.adj_matrix == other.adj_matrix def __str__(self): res = '' for row in range(3): res += ' '.join(map(str, self.adj_matrix[row])) res += ' ' return res def _clone(self): p = EightPuzzle() for i in range(3): p.adj_matrix[i] = self.adj_matrix[i][:] return p def _get_legal_moves(self): """Returns list of tuples with which the free space may be swapped""" # get row and column of the empty piece row, col = self.find(0) free = [] # find which pieces can move there if row > 0: free.append((row - 1, col)) if col > 0: free.append((row, col - 1)) if row < 2: free.append((row + 1, col)) if col < 2: free.append((row, col + 1)) return free def _generate_moves(self): free = self._get_legal_moves() zero = self.find(0) def swap_and_clone(a, b): p = self._clone() p.swap(a,b) p._depth = self._depth + 1 p._parent = self return p return map(lambda pair: swap_and_clone(zero, pair), free) def _generate_solution_path(self, path): if self._parent == None: return path else: path.append(self) return self._parent._generate_solution_path(path) def solve(self, h): """Performs A* search for goal state. h(puzzle) - heuristic function, returns an integer """ def is_solved(puzzle): return puzzle.adj_matrix == _goal_state openl = [self] closedl = [] move_count = 0 while len(openl) > 0: x = openl.pop(0) move_count += 1 if (is_solved(x)): if len(closedl) > 0: return x._generate_solution_path([]), move_count else: return [x] succ = x._generate_moves() idx_open = idx_closed = -1 for move in succ: # have we already seen this node? idx_open = index(move, openl) idx_closed = index(move, closedl) hval = h(move) fval = hval + move._depth if idx_closed == -1 and idx_open == -1: move._hval = hval openl.append(move) elif idx_open > -1: copy = openl[idx_open] if fval

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.