This is a program that solves the famous wooden tile puzzle invented by Loyd. The puzzle consists of 9 wooden tiles, placed inside a restricted-boundary board using a specific configuration. Usually the following configuration is used as the default one:
The object of the puzzle is to move the large square to the top left corner, by utilizing the empty spaces found at the bottom middle of the board. Occasionally, other default starting configurations have been used, like this one:
One particular solution, looks like this:
The following program solves Loyd's puzzle by a brute-force recursive approach. The solution is not optimal, since at the time the author programmed this (1990) he was not really interested in such solutions, only in actually finding a solution.
The program allows for a manual search as well and one could conceivably advance the search to a certain point and have the program search from there.
The program accepts a TEXT file on input, which contains the initial configuration. On pressing the "Solution" button, the program outputs to a TEXT file the moves, as they have been determined, that bring the puzzle to its final configuration.
Puzzle Encoding and Input File
Tiles are described using id's:
Vertical tile id's: 0,1,2,3
Horizontal tile id's: 4,5
Square tile: 6
Small square tiles: 7,8
Empty spaces: 9,10
The input file format (TEXT) describes the initial configuration as follows:
first four lines, tile descriptor id's, as follows:
4 4 7 6 6
5 5 8 6 6
0 1 9 2 3
0 1 10 2 3
next are the TOP-LEFT coordinates (row, column) for all the tiles. These coordinates
are shown above in red.
1 1
2 1
3 1
3 2
1 3
2 3
1 4
3 4
3 5
A different initial configuration, such as the one shown on the second figure,
above, needs the following TEXT file input:
4 4 7 2
3
5 5 8 2 3
0 1 9 6
6
0 1 10 6 6
1 1
2 1
3 1
3 2
1 3
2 3
1 4
1 5
3 4
Running the Program
To run the program, load the project and select Go from the Run menu. You will be prompted for a file name. Give the program either one of the files: "Loyd1.dat" or "Loyd2.dat" (or a different configuration of your own, but make sure you understand properly the board's initial encoding).
Input the size of the square tiles (64 is best).
Then click on the "Search" button". At the end of the run, you may optionally click the "Solution" button to display the found solution. The solution is always described using moves which are related to the TOP-LEFT coordinate of a tile, always.
Download the entire THINK Pascal project here[1].
Implementation
The project was completed while the author was a senior at the U of I in 1990. It could probably be optimized much further and can be made to avoid lots of redundant moves which creep in the final solution[2].
The solution the program finds is most likely not optimal but the author really can't bother further with understanding his own code from 13 years ago. Users and programmers may still find some of the tricks useful, such as board position encoding to avoid already searched positions and encoding of a strange board shape. It could probably be encoded more efficiently, but at the time the author was concerned more about finding a solution and less with efficiency.