15 Puzzle #2

[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 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:

1

2

3

4
5 6 7 8
9 10 11 12
13 14 15  

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:

bullet Tile images have been improved to have a 3D look.
bullet The statistics record now shows the initial configuration as well as the solution path if a solution is found.
bullet The user can now enter a "manual setup" mode   to make any desired initial arrangement.
bullet Fixed a bug which calculated parity improperly if empty space was in top left corner.

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

Suggestions for further exploration

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

Find other published solutions to check my results.  (The referenced Korf paper documents 10 optimum solutions found for random boards on the 5X5 board with run times from 2 hours to 3 months and with 8 billion to 8 trillion nodes generated per solution.  I'd say that optimal solutions are hard to come by.)

One of the Java programs on the web discusses using Priority Queues data structure to retrieve items by FVal - check this out.

Hash efficiency - distribution of hashed keys.  

Set board length to 0 before saving TMoveObj's to lists and reconstitute it from key information when needed at retrieval time.  (To conserve memory.) 

Use a database to save the Checked and Active configurations.  This would leave only the FVal list in memory.  Runs would be slower be memory constraints should be relieved. 

 
Created: November 20, 2000

Modified: February 18, 2016

 

  

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.