15-puzzle help

download 15-puzzle program


The 15-puzzle is a sliding tile puzzle.
Above picture shows the solved state.
In an original (unsolved) state the tiles are not positioned sequentially.
This program helps solving 15-puzzles in the following ways:
    - save and open games
    - generate a random game or create own puzzle
    - solve puzzles by hand
    - step through solutions
    - have the program search for a solution
In the following description [main menu][submenu] notation is used to show menu selections.

Saving and loading games

[file][save as].........self explanetory.

There is no filename extension.
The puzzle names are automatically prefixed by P15-

Generating a puzzle

[set game] [random]
Starting at the solved state, the program randomly moves the empty space.
The number of steps is selectable by the offset move count (left) rotation button.
[set game][extreme] selects one of the most difficult puzzles.

To move a tile:
Mouse Down/Up moves the tile to the neighbouring empty space.

To exchange tiles:
mouse down on tile-1-, keep mousebutton down and move, release mousebutton over tile-2-
exchanges tiles-1- and -2-.
Caution: exchanging tiles may result in unsolvable games.


[play] allows to shift a tile by mouseclick.
[play][original] reloads the original puzzle.
[play][store] sets the current puzzle as the original.
[play][back] takes back the last move.

Stepping through solutions

T : show last move
+ : show next move
- : show previous move
0 : show originalgame
Note: to show all moves sequentially click [+] or [-] with right mousebutton.

Solving a game by program

[solve][original] resets the game to the original state.
[solve][partial] tries to set the right tiles in the selected (blue edge) positions.
A mouseclick on a tile flips the selected state.

[solve][reduce] try to shorten a solution.

General considerations regarding game solving
Before solving a game, set the search depth and the search mode: breadth- or depth-first.
The breadth-first method always finds the shortest solution, but depth-first is faster in general.

It has been proven that every game may be solved in ultimately 80 steps.
In formula t = 0.136*2.1^m............t is search time in microseconds for a search depth of m moves.
So a search depth of 20 moves maximally would take 400 milliseconds.
A search depth of 30 moves may take 10 minutes, about doubling for each extra move.
This makes it totally impossible to have the computer search for full solutions.
A total solution always is the sum of partial solutions.

Select 1,2,.... tiles (blue edge)
select search depth, search mode, press [solve][partial]
The program tries to move only the selected tiles in the right position
within the selected number of steps.
If no solution is found within the search depth, increase the search depth
(at the cost of longer processing times)
or select less tiles.
If solution found, select more tiles and press [solve][partial] again.
Continue until all tiles are selected.
Press [solve][reduce] in an attempt to shorten the solution.

By a search depth of 20 and one by one tile section every game is solved within half a second.
The solution however is very long (100 moves after reduction for extreme puzzle).

Shorter solutions are obtained by selecting more tiles and setting a higher search depth.
The more tiles are selected to more efficient solutions are found at the cost of very long processing times.

Have fun !

goto Delphi program description.