Assignment #1:
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)

Resources for the assignment: