Create a python file that implements the states, operators, and heuristics needed for the eight puzzle problem. The EightPuzzle class should inherit from the InformedProblemState class. Make sure the operators make a copy of the current state before moving the tiles.

Test the solution on the following starting states A-H using the same goal each time. State A should take 2 steps, state B should take 6 steps, and state C should take 8 steps. You'll need to determine the length of the other solutions.

 1 2 3 1 3 1 3 4 1 3 7 1 2 8 1 2 2 6 3 7 3 4 7 4 5 8 4 8 2 4 8 6 2 4 2 5 8 3 7 4 4 5 6 1 5 6 3 7 6 5 7 6 5 7 5 8 7 6 6 5 4 6 5 3 1 8 7 8 2 8 1 2 goal A B C D E F G H 

In order to demonstrate that A* is superior to standard BFS and that the Manhattan distance heuristic is more informed than the tiles out of place heuristic, compare the number of nodes that each search expands on the problems given above (A-H). The only change you'll need to make to do a BFS search rather than an A* search is to replace the priority queue with the standard queue that we used in the previous question. One easy way to do this is to always have a heuristic, but in BFS have the heuristic always return 0. Convince yourself that this is equivalent to BFS. Inside a comment in the eight puzzle file, create and fill in the following table:

 Node Expansions Problem BFS A*(tiles) A*(dist) A B C D E F 

from pq import * from search import *

class InformedNode(Node): """ Added the goal state as a parameter to the constructor. Also added a new method to be used in conjunction with a priority queue. """ def __init__(self, goal, state, parent, operator, depth): Node.__init__(self, state, parent, operator, depth) self.goal = goal def priority(self): """ Needed to determine where the node should be placed in the priority queue. Depends on the current depth of the node as well as the estimate of the distance from the current state to the goal state. """ return self.depth + self.state.heuristic(self.goal)

class InformedSearch(Search): """ A general informed search class that uses a priority queue and traverses a search tree containing instances of the InformedNode class. The problem domain should be based on the InformedProblemState class. """ def __init__(self, initialState, goalState): self.expansions = 0 self.clearVisitedStates() self.q = PriorityQueue() self.goalState = goalState self.q.enqueue(InformedNode(goalState, initialState, None, None, 0)) solution = self.execute() if solution == None: print("Search failed") else: self.showPath(solution) print("Expanded", self.expansions, "nodes during search") def execute(self): while not self.q.empty(): current = self.q.dequeue() self.expansions += 1 if self.goalState.equals(current.state): return current else: successors = current.state.applyOperators() operators = current.state.operatorNames() for i in range(len(successors)): if not successors[i].illegal(): n = InformedNode(self.goalState, successors[i], current, operators[i], current.depth+1) if n.repeatedState(): del(n) else: self.q.enqueue(n) return None

class InformedProblemState(ProblemState): """ An interface class for problem domains used with informed search. """ def heuristic(self, goal): """ For use with informed search. Returns the estimated cost of reaching the goal from this state. """ self.goal = goal

abstract()