Implement A* search to solve this 8puzzle problem. Use source code included and complete the functions with
Question:
Implement A* search to solve this 8puzzle problem. Use source code included and complete the functions with comments TODO
MUST DEFINE THREE SEPARATE FUNCTIONS USING THE CODE BELOW:
1. def _compute_heuristic_cost(self):
2. def can_move(self, direction):
3. def gen_next_state(self, direction):
class PuzzleState():
SOLVED_PUZZLE = np.arange(9).reshape((3, 3))
def __init__(self,conf,g,predState):
self.puzzle = conf # Configuration of the state
self.gcost = g # Path cost
self._compute_heuristic_cost() # Set heuristic cost
self.fcost = self.gcost + self.hcost
self.pred = predState # Predecesor state
self.zeroloc = np.argwhere(self.puzzle == 0)[0]
self.action_from_pred = None
def __hash__(self):
return tuple(self.puzzle.ravel()).__hash__()
def _compute_heuristic_cost(self):
TODO
def is_goal(self):
return np.array_equal(PuzzleState.SOLVED_PUZZLE,self.puzzle)
def __eq__(self, other):
return np.array_equal(self.puzzle, other.puzzle)
def __lt__(self, other):
return self.fcost < other.fcost
def __str__(self):
return np.str(self.puzzle)
move = 0
def show_path(self):
if self.pred is not None:
self.pred.show_path()
if PuzzleState.move==0:
print('START')
else:
print('Move',PuzzleState.move, 'ACTION:', self.action_from_pred)
PuzzleState.move = PuzzleState.move + 1
print(self)
def can_move(self, direction):
TODO
def gen_next_state(self, direction):
TODO
# load random start state onto frontier priority queue
frontier = queue.PriorityQueue()
a = [3, 1, 2, 4, 7, 5, 0, 6, 8]
start_state = PuzzleState(a,0,None)
frontier.put(start_state)
closed_set = set()
num_states = 0
while not frontier.empty():
# choose state at front of priority queue
next_state = frontier.get()
# if goal then quit and return path
if next_state.is_goal():
next_state.show_path()
break
# Add state chosen for expansion to closed_set
closed_set.add(next_state)
num_states = num_states + 1
# Expand state (up to 4 moves possible)
possible_moves = ['up','down','left','right']
for move in possible_moves:
if next_state.can_move(move):
neighbor = next_state.gen_next_state(move)
if neighbor in closed_set:
continue
if neighbor not in frontier.queue:
frontier.put(neighbor)
print('Number of states visited =',num_states)
Thermodynamics An Engineering Approach
ISBN: 978-0073398174
8th edition
Authors: Yunus A. Cengel, Michael A. Boles