[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

Problem Description

The 15 Puzzle is another classic puzzle made famous in the 19th century when Sam Loyd,  a recreational mathematician, produced a commercial copy that was was unsolvable.   What a dirty trick!   The puzzle consists of a 4X4 board or frame with 15 sliding tiles, numbered 1 to 15.   The objective is to get them into some predefined pattern.  In our case like this:

Background & Techniques

Looking at possible configurations of the board:  If we consider the empty slot as a tile, there are 16 choices for the top left square, 15 for the second, 14 for the 3rd, etc.  i.e. 16! (16 factorial - a large number) arrangements in total.  Without picking up tiles (i.e. sliding only), only half of these positions are achievable from any starting configuration  - still a very large number indeed ( over 20 digits long). 

Loyd, in his unsolvable version, reversed the 14 and 15 tiles and then asked players to solve the puzzle as above.  His arrangement allowed solutions from the "other half" of the configuration space, but not the requested one.  (I remember as a youngster, prying the plastic sliders out of the board to rearrange them in the desired configuration.  I don't think I had one of the insolvable versions, it just seemed like the quickest means to an end.)  

In our version, the prying of sliders is not possible or necessary.  My original intention was to publish this program with an auto-solve button enabled.  That has turned out to be not so easy, so I've decided to publish the manual version this week and the auto-solve version next week.     

The puzzle defines a TSliderBoard object, descended from TPanel to represent the board.   Most of the information is contained in two  arrays: a TBoard array of TBoardRec records, each containing the index of the slider associated with this square, and a TSliders array containing TPanel components that represent the individual tiles.   For ease of access, both arrays are only singly dimensioned.  For an NxN board,  zero based column and row numbers are calculated as index mod N and index div N  as required.  Column and row values are kept in the TBoardRec records, so that they do not have to be calculated very often.  

So anyway, you can study the code here to see how tiles are managed and  the implementation of the "Scramble" button.   And even practice solving the problem.   Next time we'll probably be learning more about the Manhattan heuristic and   A* search algorithms.  (See 15puzzle_2.htm for Version 2 with Auto-solve)

Running/Exploring the Program

Revised: May 15, 2018