15 Puzzle #1

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

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

 

   

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

Suggestions for further exploration

You could implement the "Auto-Solve" feature if you feel really ambitious.  It is non-trivial, I hope, since I've spent a couple of days working on it so far.

The program could display another form with solution choices on it.  A search of the web will show some of the other solution patterns (zigzag and spiral come to mind).  The program should then monitor moves and recognize when the solution configuration has been achieved.  

The  objects were designed to work with non-square arrays, but I didn't get a chance to test them.  Someone really should do that.  I think the 4X2 arrangement might be useful it creating the auto-solver, at least I find myself working with 4X2 subsets of the board when I solve it manually.

 

Revised: July 23, 2016