Create a python file that implements the states, operators, and heuristics neede
ID: 3871508 • Letter: C
Question
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.
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:
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()
Explanation / Answer
eightPuzzle.py
from informedSearch import *
class PuzzleState(InformedProblemState):
"""
The state of the puzzle is a 3x3 matrix of numbers 1-8. The goal state will
look like this:
1 2 3
8 0 4
7 6 5
The objective is when given a non-goal state to swap a number with the
black space to reach the goal state. No diagonal moves are allowed and
moves cannot be made to wrap around the board.
Data Structures:
puz (eight puzzle) = '123804765'
0: the empty space
Node Expansions
Problem BFS A*(tiles) A*(dist)
a 4 3 3
b 77 8 7
c 179 18 10
d 666 48 20
e 809 44 20
f 1843 110 123
g 5396 375 61
h 48707 3290 186
"""
def __init__(self, puz):
self.puz = puz
def __str__(self):
"""
Required method for use with the Search class.
Returns a string representation of the state.
"""
return self.puz
def illegal(self):
"""
Required method for use with the Search class.
Tests whether the state is illegal. Illegal states return -1 from the
operator.
"""
if self.puz == -1: return 1
#legal state
return 0
def equals(self, state):
"""
Required method for use with the Search class.
Determines whether the state instance and the given
state are equal.
"""
return self.puz == state.puz
def movL(self):
"""
Moves zero value one space left. If it is in the left column it will
return -1
"""
i = self.puz.index('0')
if i not in (0, 3, 6):
index = i - 1
newPuz = ""
newPuz = self.puz[0: index] + '0' + self.puz[index] + self.puz[i + 1:]
return PuzzleState(newPuz)
return PuzzleState(-1)
def movR(self):
"""
Moves zero value one space right. If it is in the right column it will
return -1
"""
i = self.puz.index('0')
if i not in (2, 5, 8):
j = i + 1
newPuz = ""
newPuz = self.puz[0: i] + self.puz[j] + '0' + self.puz[j + 1:]
return PuzzleState(newPuz)
return PuzzleState(-1)
def movUp(self):
"""
Moves zero value one space up. If it is in the top row it will return
-1
"""
i = self.puz.index('0')
if i not in (0, 1, 2):
j = i - 3
newPuz = ""
newPuz = self.puz[0: j] + '0' + self.puz[j + 1: i] + self.puz[j] + self.puz[i + 1:]
return PuzzleState(newPuz)
return PuzzleState(-1)
def movDn(self):
"""
Moves zero value one space up. If it is in the bottom row it will
return -1
"""
i = self.puz.index('0')
if i not in (6, 7, 8):
j = i + 3
newPuz = ""
newPuz = self.puz[0: i] + self.puz[j] + self.puz[i + 1: j] + '0' + self.puz[j + 1:]
return PuzzleState(newPuz)
return PuzzleState(-1)
def operatorNames(self):
"""
Required method for use with the Search class.
Returns a list of the operator names in the
same order as the applyOperators method.
"""
return ["movL", "movR", "movUp", "movDn"]
def applyOperators(self):
"""
Required method for use with the Search class.
Returns a list of possible successors to the current
state, some of which may be illegal.
"""
return [self.movL(), self.movR(), self.movUp(), self.movDn()]
def heuristic(self, goal):
"""
Required method for use with InformedSearch class.
Executes Manhattan Distance, Tiles Out of Place or Breadth First
Search heuristics if uncommented.
"""
#sum = 0
#sum = PuzzleState.outOfPlace(self, goal
sum = PuzzleState.manhattan(self, goal)
return sum
def manhattan(self, goal):
"""
Finds the Manhattan Distance (up, down, left, right distance) from
the goal state for each value of the matrix and returns the sum.
"""
sum = 0
for i in goal.puz:
sum += abs(self.puz.index(i) - goal.puz.index(i))
return sum
def outOfPlace(self, goal):
"""
Returns the number of values out of place from the matrix.
"""
sum = 0
for i in range(0, 9):
if self.puz[i] != goal.puz[i]:
sum += 1
return sum
#goal state
goal = '123804765'
#test states
a = '130824765'
b = '134862075'
c = '013425876'
d = '712803654'
e = '812704653'
f = '263405187'
g = '734615802'
h = '745603812'
#search test states
InformedSearch(PuzzleState(a), PuzzleState(goal))
InformedSearch(PuzzleState(b), PuzzleState(goal))
InformedSearch(PuzzleState(c), PuzzleState(goal))
InformedSearch(PuzzleState(d), PuzzleState(goal))
InformedSearch(PuzzleState(e), PuzzleState(goal))
InformedSearch(PuzzleState(f), PuzzleState(goal))
InformedSearch(PuzzleState(g), PuzzleState(goal))
InformedSearch(PuzzleState(h), PuzzleState(goal))
InformedSearch.py
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.
"""
#abstract()
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.