Question: ***************PLEASE PRINT OUTPUT********************* ***************USE CODE PROVIDED.*********************** Overview: The assignment, Assignment A, involves Search Algorithms, in particular, Breadth-First, Depth-First, and A-Star. It involves a program that
***************PLEASE PRINT OUTPUT*********************
***************USE CODE PROVIDED.***********************
Overview:
The assignment, Assignment A, involves Search Algorithms,
in particular, Breadth-First, Depth-First, and A-Star.
It involves a program that simulates a puzzle called an N-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
search.py
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
Software Requirements:
You must be using python3
Assignment:
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
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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help