Build a n-sliding block puzzle solver
In the class, we have seen the 8-puzzle example. The 8-puzzle is a classic problem in AI that can be solved fairly easily with different search strategies, such as the Breadth First Search and A*.
However, the 15-puzzle version of the same game is not that easy to solve. In fact, only Iterative Deepening A* (IDA*) are able to resolve a 15-puzzle relatively fast and without consuming too much memory. A* and IDA* algorithms use heuristic function to find the optimal solution. Three heuristic functions are proposed : Manhattan Distance, Linear Conflict and Database Pattern.Goal:
The goals of this assignment are:
- Build a 15-puzzle random generator that produces random but solvable initial states. Note that not all randome states are solvable (Solvability of the Tiles Game by Mark Ryan)
- Build a solver of the 15-puzzle game using either IDA* (or something better for extra credits +2).
- Extend the 15-puzzle problme to n-puzzle problem (for extra credits +3).
Total credits: 5 pts (+ 5 pts extra credits)