The 15-puzzle problem

The 15-puzzle is a larger version of the 8-puzzle.

Goal:

15	14	13	12
11	10	9	8
7	6	5	4
3	2	1

Initial

11	5	2	1
14	8	10
15	4	13	6
9	12	3	7

For this assignment, you will implement the two uninformed search algorithms that find solutions to the 15-puzzle problem. You are requested to implement the programs to the 15-puzzle problem using:

1. Depth-first search (DFS)

2. Breadth-first search (BFS)

For each of the search routines, avoid returning to states that have already been visited on the current solution path i.e., there should be no repeated states in a solution.