Implement bfs, and dfs to solve a 8 puzzle.

Use code provided only

Do not answer if you do not have a perfect solution

Input to search function puzzle = [[0, 2, 3], [1, 5, 6], [4, 7, 8]] goal_state= [[1, 2, 3], [4, 5, 6], [7, 8, 0]] Expected Output [UP, UP, LEFT, LEFT], using the ENUMS defined in search.py

0 represents the empty space Ties should be broken in the order: UP DOWN LEFT RIGHT The goal state has the 0 in the bottom right

here is my main.py

```from search import BFS, DFS, A_Star_H1, A_Star_H2, UP, DOWN, LEFT, RIGHT

def get_move_string(moves): """ Helper function to print moves.

""" move_string = "" if len(moves) == 0: return "NONE" for move in moves: if move == UP: move_string = move_string + "U " elif move == LEFT: move_string = move_string + "L " elif move == DOWN: move_string = move_string + "D " elif move == RIGHT: move_string = move_string + "R " else: move_string = move_string + "INVALID " return move_string

puzzle = [[ 4, 1, 3], [7, 2, 5], [8, 6, 0]] moves = BFS(puzzle) print(" BFS | " + get_move_string(moves))

puzzle = [[ 4, 1, 3], [7, 2, 5], [8, 6, 0]] moves = DFS(puzzle) print(" DFS | " + get_move_string(moves)) ```

and here is my search.py ``` # ENUMS UP = 0 LEFT = 1 DOWN = 2 RIGHT = 3

def BFS(puzzle): """ Breadth-First Search.

Arguments: - puzzle: Node object representing initial state of the puzzle

Return: final_solution: An ordered list of moves representing the final solution. """

final_solution = []

# TODO: WRITE CODE

return final_solution

def DFS(puzzle): """ Depth-First Search.

Arguments: - puzzle: Node object representing initial state of the puzzle

Return: final_solution: An ordered list of moves representing the final solution. """

final_solution = []

# TODO: WRITE CODE

return final_solution ```