The 8-puzzle was one of the earliest heuristic search problems. The object of th

Question

The 8-puzzle was one of the earliest heuristic search problems. The object of the puzzle is to slide the tiles horizontally or vertically (see pp.103, fig.3.28) into the empty space until the configuration matches the goal configuration. Two simple heuristics for the 8-puzzle/15-puzzle were given: Manhattan distance and misplaced tiles. Implement A* npuzzle.py program in Python using both heuristics and comparing the performance of the resulting algorithms. You define the initial and terminal configurations. You decide whether program will produce output as sequence of configurations graphically or as text. Please include code for it

Explanation / Answer

from heapq import heappush, heappop from random import shuffle import time class Solver: def __init__(self, initial_state=None): self.initial_state = State(initial_state) self.goal = range(1, 9) def _rebuildPath(self, end): path = [end] state = end.parent while state.parent: path.append(state) state = state.parent return path def solve(self): openset = PriorityQueue() openset.add(self.initial_state) closed = set() moves = 0 print 'tentando resolver:' print openset.peek(), ' ' start = time.time() while openset: current = openset.poll() if current.values[:-1] == self.goal: end = time.time() print 'achei uma solução' path = self._rebuildPath(current) for state in reversed(path): print state print print 'resolvido com %d movimentos' % len(path) print 'encontrei a solução em %2.f segundos' % float(end - start) break moves += 1 for state in current.possible_moves(moves): if state not in closed: openset.add(state) closed.add(current) else: print 'não consegui solucionar!' class State: def __init__(self, values, moves=0, parent=None): self.values = values self.moves = moves self.parent = parent self.goal = range(1, 9) def possible_moves(self, moves): i = self.values.index(0) if i in [3, 4, 5, 6, 7, 8]: new_board = self.values[:] new_board[i], new_board[i - 3] = new_board[i - 3], new_board[i] yield State(new_board, moves, self) if i in [1, 2, 4, 5, 7, 8]: new_board = self.values[:] new_board[i], new_board[i - 1] = new_board[i - 1], new_board[i] yield State(new_board, moves, self) if i in [0, 1, 3, 4, 6, 7]: new_board = self.values[:] new_board[i], new_board[i + 1] = new_board[i + 1], new_board[i] yield State(new_board, moves, self) if i in [0, 1, 2, 3, 4, 5]: new_board = self.values[:] new_board[i], new_board[i + 3] = new_board[i + 3], new_board[i] yield State(new_board, moves, self) def score(self): return self._h() + self._g() def _h(self): return sum([1 if self.values[i] != self.goal[i] else 0 for i in xrange(8)]) def _g(self): return self.moves def __cmp__(self, other): return self.values == other.values def __eq__(self, other): return self.__cmp__(other) def __hash__(self): return hash(str(self.values)) def __lt__(self, other): return self.score()

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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