Total Points: 25
15 puzzle is a sliding puzzle game with numbered squares arranged in 4X4 grid with one tile missing.
The puzzle is solved when the numbers are arranged in order.
The actions are defined in terms of direction where empty square can be moved to
UP (U), Down(D), Left(L), Right(R)
Write a program which performs breadth first search to find the solution to any given board position for 15 puzzle
Input
The input should be given in form of sequence of numbered tiles for initial board configuration,
‘0’ indicating the empty space (see example below) Output
1. Moves
2. Number of Nodes expanded
3. TIme Taken
4. Memory Used
Example
1 0 2 4 5 7 3 8 9 6 11 12 13 10 14 15
Moves: RDLDDRR
Number of Nodes expanded: 2642
TIme Taken: 42ms
Memory Used: 8624kb
Unsolvable puzzle
There can be some puzzle for which the solved state cannot be reached
If the solution doesn’t exist, display the message “solution cannot be found”
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14
Solution cannot be found
Hint
Check for repeated state to avoid “out of memory” error
Submission
Please submit a zip file with filename <netid_bfs.zip including following files:
● Source Code
● Readme.txt including instruction to run the code
Programming Language
You can choose from C++, Java or Python
Rubric
Print the moves to reach the solution = 10
Print “solution cannot be found” for unsolvable initial state = 3
Print number of nodes expanded = 3
Print total memory usage = 3
Print total time taken = 3
Coding style, comments, readme instruction = 3
AIMA code
You can use the code from the textbook found in following github repo https://github.com/aimacode
