Project Description
This is a fifteen puzzle written in F# with WPF. In the program, you can reset all the tiles, generate random permutation of tiles, and solve the puzzle using the build-in solving algorithm.

This is my first F# program after reading the book Real World Functional Programming. After some frustration and struggles, I gradually learned how to write F# code in a functional way. The book might interest you.

Real World Functional Programming

http://msdn.microsoft.com/en-us/library/hh314518.aspx

Required libraries for running this program

This program is written in Visual Studio 2010 with .NET Framework 4.0. So .NET Framework 4.0 and F# Runtime 2.0 are required for running the program. They can be downloaded via the following links.

.NET Framework 4.0 redistributable package
http://www.microsoft.com/download/en/details.aspx?id=17718

Visual Studio 2010 F# Runtime 2.0

http://www.microsoft.com/download/en/details.aspx?id=13450

About the 15-puzzle

The 15-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle.
http://en.wikipedia.org/wiki/Fifteen_puzzle

The solving algorithm

There are 3 steps in solving a 15 puzzle.

First, solve the first row and first column.

Then solve the second row and second column.

Finally, the 15 puzzle is reduced into 2 by 2 puzzle, with only 3 tiles not in order. Now we can only move the 3 tiles either clockwise or anticlockwise. Repeat rotating them around in one direction until the 3 tiles reach their right positions, if the case is solvable.

We can determine the solvability before solving the puzzle, see the article below about how to determinate the solvability of the puzzle.

http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

Steps with illustrations

Step 1, solve the first row and first column.

Step 2, solve the second row and second column.

Step 3, solve the last 3 tiles.

How to make a move

To move a tile to one of its adjacent positions, we can move the blank to that position first, and then move the blank to the position of the tile.

Figure 1

For example, as in Figure 1 (the screenshot above), if we want to move 15 to 14's position, we first move the blank to 14's position without moving 15 itself. To do this, we have to go around 15, move the blank along 12, 11, 10, and finally 14, as in Figure 2. Once the blank is at the target position (14's position in figure 1), we can simply move the blank to 15, (or say move 15 to the blank, it's the same) then 15 will be at the target position, as in Figure 3.

Figure 2

Figure 3

If we want to move a tile to a farther position (not adjacent to itself), we can do the routine above several times. The tile will move one step at each time. In this program, both the path to move the blank and the path to move the tiles are obtained by a breadth-first search. The search is performed on a grid that regard the current tile to be moved (15 is the above example) and all the finished rows and columns as obstacles.

Last edited Feb 24, 2012 at 10:52 AM by lsz0, version 46