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

Problem Description

The 15 Puzzle is another classic puzzle made famous in the 19th century by puzzleist Sam Loyd.   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:

This  expanded version includes other sizes, target patterns and an auto-solve facility.

Background & Techniques

Here's version 2 - still very much a work in progress.  The problem is a lot harder than I had realized when I started.   So here's an update with some more information.  The auto-solve technique used is an algorithm call A-Star (or Iterative Deepening A-Star, IDA*).  Here's the idea.  We estimate how far we are from the solution using a distance function commonly called the "Manhattan" heuristic.   I assume the name derives from the fact that we are measuring moves like city blocks in the horizontal and vertical direction.  Specifically, the MoveScore of any particular configuration is the sum of the horizontal and vertical distances of each tile from its target location.   These are accumulated in a CumScore field. We keep two lists of new TMoveObj objects, an active (open) list and a checked (closed) list.  Each TMoveObj contains information about the board configuration, where we came from, and the scores for this board.  

In a loop  we'll take the configuration from the active list with the lowest FVal score (FVal =Weight * MoveScore + CumScore), calculate the scores for each possible next configuration and put them on the active list.  Any duplicates on either the active or checked list ( i.e. we have looped back to the same configuration we have visited before) must be recognized and the object with the lowest score retained.  At the end of each loop, the object is moved from the active list to the checked list.  This continues until we reach a configuration with a MoveScore of 0 (or the user gives up).  Each TMoveObj contains a link back to it's "parent", so when (if) we find a solution, we can reconstruct the series of moves that got us there and use that to display the solution for the user. 

MoveScore is multiplied by a Weight value before being added to FVal.  The effect is to punish moves that take us away from the solution, with the effect that solutions can be found quicker but will be further from optimum.  Weights of 50 or 100 or 200 will almost always produce a solution, albeit a long one.  Weights around 3 produce optimum or near optimum solutions, when a solution is found before running out of resources.    

I used a THashStr class to hold the ActiveByKey and CheckedByKey lists of TMoveObj items by key.  Key is simply a concatenation of string versions of tile numbers.   The ActiveByFVal list is a sorted TStringList used to retrieve the configuration with the lowest FVal to be checked next.       

There are some nominal improvements to the Manhattan heuristic, namely "Linear Conflict", "Corner Tiles",  and "Last Moves" .  For more information search out the paper "Finding Optimal Solutions to the Twenty-Four Puzzle" by Richard E. Korf and Larry A. Taylor.    Just to give you an idea, a "Linear Conflict" arises when to 2 tiles are in  reversed position in their target row or column.   The Manhattan heuristic in this case does not account for the fact that one or the other of these tiles must move out of line to let the other get past, so 2 squares can be added to the MoveScore for each such occurrence.  

Here are some of the known problems - 1) The distance heuristic doesn't converge very fast for small weight values, there may be hundreds or thousands of configurations that are the same distance from the solution.   2) The items in the active list must be accessed in two sequences, by FVal to get the low score so far,  and by configuration key to detect duplicates.   This increases memory usage   Currently the hashed lists start with a table size of 100,000 with a max loading factor of 50%.  So rehashing occurs after 50,000 table entries have been created.   3) Memory constraints and size of the lists will eventually slow access to an unacceptable level.    4) The additional heuristics should, in theory,  check for duplicates, i.e., if the same tile is involved in a linear conflict and a corner tile conflict, the extra moves should only be added one time - these checks are not yet implemented.

Have at it!  I've had about all the fun I can stand for awhile with this problem.

Addendum March 26, 2006:  Posted version 3.   It has been a long time since we visited this puzzle.  Recently a viewer  wrote asking about (and doubting)  the fact that only half of the tile arrangements were solvable.   After a couple of email attempts failed, I resorted to modifying the program to allow the user to view the "parity" of the configuration anytime by pressing the "P" key.  User can also "cheat", exchange a random adjacent pair of tiles by pressing "C".   Any odd number of such exchanges results in a unsolvable configuration.   Parity is defined as the even/odd value of a sum determined as  follows:  

1. List numbers from left to right and top to bottom, ignoring the empty space.
2. Sum the number of inversions.  An inversion value for each tile is the number of tiles to its left which are greater than, (or the number to the right which  the less  than) its value.
3. If the number of columns in the puzzle is even, add the row number of the empty tile space..  

The result may be even or odd depending  on puzzle size,  but will always be the same after moves are made unless tiles are exchanged.  About half the time, exchanging two random tiles for a solvable puzzle will change the parity and make the puzzle insolvable.  Exchanging two adjacent tiles will always do so.    

Addendum January 7, 2007:  A French mathematician , Claude Dellacherie, recently wrote with some interesting information he is collecting for an upcoming presentation.  Our program made the "final 4" of the programs he has investigated for his talk.  I made a few changes at his request and posted version 3.1 today.  Changes include:

I had intended to add a backup/restore option but we'll save that for another time.  Claude did find a version of the puzzle which replaces "Manhattan Distance" with a "Walking Distance" measurement for the estimated distance to a solution and seems  to work much faster    Unfortunately the description seems to be in Japanese only.  Let me know if you know more about this program and the algorithm it uses.  

Running/Exploring the Program

Here are the items I'm planning to investigate (eventually):

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.