The assignment 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 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 Assignment: Implement (20 pt) Breadth First Search, (20 pt) Depth First Search, (20 pt) A-Star with the heuristic: # of misplaced tiles (20 pt) A-Star with the heuristic: Sum of Manhattan Distance of each tile from correct position. Compare (20pt): Which algorithm performed the fastest, which took up the most memory and which gave the best solution. Include your answers in the README Include a README with your code telling me how to run it, any requirements or dependencies, and the answers to the comparison questions above. Submit ONE python file called 'search.py' and ONE README called README.txt

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

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

# 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