PLEASE HELP WITH ARTIFICIAL INTELLIGENCE IN PYTHON. PLEASE DO A HUGE FAVOR BY SOLVING SEARCH.PY, I'LL DEFINETELY UPVOTE IF THE SOLUTION FOR SEARCH.PY IS CORRECT!!!

The project involves Search Algorithms, in particular, Breadth-First, Depth-First, and A-Star. It involves a program that simulates a puzzle called an N-Puzzle: https://en.wikipedia.org/wiki/15_puzzle In our version, the blank space is in the bottom right in the solution and we are working on 3x3 puzzles Files: main.py A driver (test file) used to run your code (All Algorithms) on all the examples. I have given you 3 examples, and will graded your code against these 3, as well as several others (of similar size) search.py A file with 4 algorithms that you will write as your assignment, BFS, DFS, and 2 A-Stars. A shell has been included for each. Be sure to return the correct expected values. Example: Input File: 0 2 3 1 5 6 4 7 8 Input to search function puzzle = [[0, 2, 3], [1, 5, 6], [4, 7, 8]] Expected Output [UP, UP, LEFT, LEFT], using the ENUMS defined in search.py Running: python3 main.py Implement Breadth First Search, Depth First Search, A-Star with the heuristic: # of misplaced tiles A-Star with the heuristic: Sum of Manhattan Distance of each tile from correct position.

Notes: 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 Be sure to submit clean, working code.

Main.py (Please don't change)

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

def read_puzzle(filename):

"""

Helper to read a puzzle from a file.

Arguments:

filename: Name of file to read from.

"""

puzzle = []

with open(filename, "r") as f:

for line in f.readlines():

puzzle.append(line.split(' '))

return puzzle

def run_test(size, filename):

"""

Takes a filename,

then creates a puzzle,

reads it in from file,

and runs each of the search algorithms

"""

print(f"{filename}:")

puzzle = read_puzzle(filename)

moves = BFS(puzzle)

print(" BFS | " + get_move_string(moves))

puzzle = read_puzzle(filename)

moves = DFS(puzzle)

print(" DFS | " + get_move_string(moves))

puzzle = read_puzzle(filename)

moves = A_Star_H1(puzzle)

print(" A* H1 | " + get_move_string(moves))

puzzle = read_puzzle(filename)

moves = A_Star_H2(puzzle)

print(" A* H2 | " + get_move_string(moves))

print("-" * 20)

run_test(3, 'test_data/ex1.txt')

run_test(3, 'test_data/ex2.txt')

run_test(3, 'test_data/ex3.txt')

Search.py (Please solve this)

# 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

def A_Star_H1(puzzle):

"""

A-Star with Heuristic 1

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 A_Star_H2(puzzle):

"""

A-Star with Heauristic 2

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

ex1.txt

0 2 3 1 5 6 4 7 8

ex2.txt

1 2 0 8 5 3 4 7 6

ex3.txt

4 1 3 7 2 5 8 6 0