Description
Task 1
Write a Python program to solve the 8-Puzzle. Please see
https://en.wikipedia.org/wiki/15_puzzle
for the puzzle description.1 Specifically, your program needs to do the following:
Randomly generate an 8-puzzle board that has a solution. (Hint: Use your favourite search
engine to find conditions for solvable 8-puzzles.)
Solve the puzzle.
Run your program multiple times and record the average processing time and the average number
of moves.
Task 2
Use a different algorithm to solve the 8-puzzle and compare the result with your solution from Task
1. E.g., if you have used Greedy search in Task 1, use A∗
in Task 2 or vice versa.
1Since there is no Wikipedia page for the 8-Puzzle, let’s just use the 15-puzzle page instead.