CS 480 Artificial Intelligence
fall 2009
Project # 3 Due: October 9, 2009
The text book
discusses the well-known 8-puzzle. The commercial version of this puzzle has 15
tiles (in a 4 x 4 arrangement) and has been a top selling puzzle for more than
one hundred years. In this project, we will consider a variation of this puzzle
called Missing Link which is shown below:
The following
description of this puzzle was taken from http://www.jaapsch.net/puzzles/missing.htm
“This puzzle
consists of a square tower of four layers. On the sides are sliding tiles, and
each side depicts a chain in different color. One chain, the white one, is made
of only three tiles, so that there is a gap. The tiles can slide up and down
into the gap. The top and the bottom layer can rotate so that the pieces from
different chains are mixed up.”
Solution state
is one which all the links are of the same color in each row – to be specific
we want the solution to have the links red, yellow, green and white as shown in
the figure below. It will be convenient to label each of the pieces with a
number between 1 and 15.
The web site
also has a program in Javascript that allows you to
make moves. This Javascript program works on a
flattened version of the puzzle that makes its similarity to 15 puzzle more
transparent.
You are to write
a program that implements A* algorithm as well as iterative deepening algorithm
to find the shortest path solution to Missing Link from an arbitrary starting
state. Here each sliding move or a rotation is considered as a unit cost move.
(A quarter rotation or half rotation clockwise or
counterclockwise is considered as a basic move and each of them counts as a unit
cost move.)
Specifications: Your implementation will involve a comparison
between A* algorithm and iterative deepening algorithm to solve the puzzle. In the
case of A*, the heuristic function to be used is the
