Sliding Coins Puzzle

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

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

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

Search DelphiForFun.org only

 

 

 

Problem Description

Place 3 dimes and 2 quarters in a row like this       The baseline is an extension of line formed by the bottoms of these coins.  The objective is to rearrange the coins into an arrangement that looks like this   .    You can only move a pair of adjacent coins of different types (i.e. Dime/Quarter or Quarter/Dime) by sliding the pair left or right to a new unoccupied location anywhere on the baseline. (If you are using real coins, you'll have to slide them vertically first, then left or right, then back in line.)   Coins may not be rotated to change orientation while moving     

Reference: The Master Book of Mathematical Recreations, Fred Schuh,  Dover Publications  

Background 

This puzzle was presented  as an example of a puzzle that can most easily be solved in reverse.   From the original position there are 4 coin pairs to consider as first move candidates.  In the solution there is only one coin pair eligible for the first move.  Since all moves are reversible, we can consider DDDQQ to be the initial state and DQDQD to be the goal state.  Reversing the order and direction of the moves to solve this puzzle is a solution to the original puzzle.  This does indeed reduce the search tree significantly.     

This program however has been implemented more as an example of graphics and drag drop processing than as a search program.   The AutoSolve button simply selects randomly from a few predefined solutions embedded in the program.   The program used to generate these solutions is (or will be) posted to Math Topics as Adjacency List Graph Searching. 

Non-programmers can skip to the bottom of the page to download an executable version of the program

Techniques

This is the first program in this series to show drag images (an image of the pair of coins being dragged) while dragging.  Dragging images seems unnecessarily complicated - I'm sure there are reasons  beyond my feeble understanding why this is so.   

Dragging without images is straightforward.  You need to specify either dmAutomatic for the control to be dragged,  and,  in the receiving control, a DragOver exit (to say that its OK to drop it here) and DragDrop exit (to actually move the dropped object).    

Image dragging is more complex.  Whenever a control drag is started, a call is made to GetDragImages which, unless you have overridden it, returns nil, telling dragging that no images are being displayed.  If you return a Timagelist  (or a TDragImageList),  drag images will be used.  To display other than the first image, a call to Imagelist.SetDragImage is required to specify which image to use.

In summary, the elements are:

bulletA TDragImageList (or TimageList) containing the images to be displayed while dragging.  
bulletA call to ImageList.SetDragImage at drag start time specifies which image to display.   If not called, dragging will show the first image in the ImageList.
bulletThe dragged object  needs a GetDragImages method to tell Windows which image list to use. GetDragImages is called automatically  when dragging begins for a control.  
bulletIf you mess with the dragged control (like hiding it or changing it's color when dragging starts, you should have an OnEndDrag exit activated to restore the visual aspects if the drag fails.   
bulletcsDisplayDragImage must be added to the ControlStyle property for any control that is to show the drag image.  Whether this is a Delphi bug or a coding problem, I'm not sure.  I found the hint in Delphi newsgroups and sure enough, without   ControlStyle := ControlStyle + [csDisplayDragImage]; in the FormCreate exit, images are not displayed.  
bulletThe TDragObject structure is only required if you specifically need to drag something other than a control (Delphi's Help text talks about several different control types using a common TDragObject).   Not used here, the default TControlDragObject seems to work fine.

This application is complicated by the fact that we are dragging pairs of objects (big/small coin pairs) and the drop area must only be able to fit the pair, ignoring the fact that the quarter may be dropping into a dime size slot.   

Anyway, it mostly works if you want to study the code for hints. 

Addendum: January 17, 2002:  I posted an improved version today with better dragging features,  specifically,  

bulletMouse cursor is now centered on the top of the drag image, rather than in the top left corner.
bulletOnDragOver exit now tests if image is over an empty slot before setting Accept flag to true - it does by calling a new DropSlot function which returns the leftmost index of  pair of empty coin slots, or -1 if image is not over empty slots. 

Running/Exploring the Program 

bulletBrowse source extract
bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

Coin drawing is still done directly on the form's canvas.  It would be cleaner to to draw on the canvas of a Timage to simplify  the calculation of offsets when converting points to screen coordinates..

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