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)