You are to write Prolog programs to solve the 8-puzzle using the “shells” discussed in class and the supplementary textbook.

You are to write Prolog programs to solve the 8-puzzle using the “shells” discussed in class and the supplementary textbook. The code for these shells is in the zip(PFA) file posted on the course website. For each run, use the same start state shown in the textbook on pages 103, 105, 141, and 205.(Artificial Intelligence,Luger,6th,2008)

(Optional, this takes several hours to run; do this only if you are curious to see if your program will actually work.) Solve the puzzle using the depth-first search algorithm. Turn in a listing of your program, together with output showing that it worked.

Solve the puzzle using depth-first search with a depth bound of 5. Turn in a listing of your program, together with output showing that it worked.

Solve the puzzle using breadth-first search. Turn in a listing of your program, together with output showing that it worked.

Solve the puzzle using best-first search with a heuristic that counts the number of tiles out of place. [Hint: My heuristic predicate is defined by 4 lines of code.] In addition, show that the heuristic is actually pruning the search space. For this it is necessary to modify the program so that it outputs a list of the nodes visited during the search, then run this once with a constant 0 heuristic and once with the tiles-out-of-place heuristic, and then compare the results. The nodes searched by the tiles-out-of-place heuristic should be a subset of those searched by the 0 heuristic. As an alternative to actually listing the nodes searched, you could instead output a count of the number of such nodes for each run. Turn in a listing of your program together with outputs as described.