Coal to Diamonds 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

This a program to solve the "Coal to Diamonds" puzzle.  In its most difficult version, 9 lumps of coal in a 3X3 grid pass through two intermediate stages before becoming a white diamond.    An item changes to the next phase when clicked.  What complicates matters is that when a lump is clicked, all items in that row and column advance to the next phase.  Items that are already diamond will revert to coal when they advance. 

Background & Techniques

This is probably not a very good puzzle for human solution, at least I have found it impossible to visualize board states more than a move or two ahead.  But it has been an interesting puzzle to analyze.

The program allows you to set up random puzzles requiring 1 to 15 moves to solve.  You can also enter any specific board start position. 

Any board that is solvable can be solved in 15 or fewer moves, however only about 6% (16,384 of 262,144) of possible boards are solvable.   The   starting position with 9 lumps of coal is one of 7  which requires 15 movies to solve.

When users are solving, moves are displayed in a list.  Clicking any move in the list will backup to that board position. There are buttons to start an "auto-solve" search for all diamonds from any board position.  

You can chiise from three search methods introduced on our Graph Traverse and Shortest Path pages.  They  are: 

  • "Depth first" follows all possible paths down to the maximum specified level looking for the goal board.  It will find solutions eventually, but the first solution found may not be the shortest.  
  • "Breadth first" tries all possible 1st moves, then from there all possible 2nd moves, etc. When  it finds a solution, it is guaranteed to be as short as any.
  • And "Dijkstra's Shortest Path" algorithm is a modified breadth first search and generally is the fastest way to find the shortest  path to a solution.     It finds the shortest distance from the starting board to each other board by working outward from the start. So for any board visited, we always know the  shortest way to get there.  Eventually we'll visit the destination node and the problem is solved.

A click on any solution found by the program will replay the solution.  You can also manually replay by clicking on the specified column and row.  Note that moves are "commutative", we can apply them in any order without changing the final result.  Also, four clicks on the same cell are the same as no clicks (Each affected cell has advanced 4 times and is back where it started.)  So in Depth first solutions, any specific move that occurs 4 or more times can be can be eliminated in groups of 4.

The program uses a "graph" describing each of the board positions and  the 9 adjacent board positions that can be reached by clicking on a board cell.  The original file with all 262,144 positions was 34 megabytes in length and required several seconds to load at program startup.  The "pruned" file currently used  contains only the 16,384 board positions which can lead to the solution and loads much faster.   The file, CoalDiamondsPrunedgraph.gph,  will be built the first time you run the program and retained from run to run thereafter.     

Non-programmers are welcome to read on, but may want to skip to the bottom of this page to download an executable version of the program.

Notes for Programmers

The program uses a slightly modified version of our library TGraphList class that adds a version of the Dijkstra  procedure which calls a "Goalfound" procedure when the solution has been found.  This makes it compatible with DepthFirst and BreadthFirst so a single procedure can handle results display for all three search types.

 I decided to identify the 4 phases (coal to diamond) with integers 0 to 3.  this meant that integer could be used to identify each board position by using 2 bits for each cell.   So the goal board (all 3's) becomes hexadecimal 3FFFF, nine "11" bit pairs.   Routines required to operate on the boards include ForwardMove  and  ReverseMove to make moves;  BoardToKey and KeyToBoard to make keys for TGraphList;  and BoardtoStringRep and StringrepToBoard to  convert board positions to and from displayable strings.

A second page contains links to several of the routines written while developing the game:  

bullet  Forward and reverse moves were a little tricky, so there is a button to take a given board position and display the next and previous board positions when a given cell is clicked.   
bullet Build the entire graph of 4board states
bullet Prune the graph to those states which can lead to the 333 333 333 goal state and write the graph to  file: "CoalDiamondPrunedGraph.gph" which is loaded at startup time.
bullet A button generates all valid games and displays the count for each game length.  This runs several hours.  The procedure  now saves the path to each solved game in TStringLists, one for each solution length with one list entry with the starting position and moves for each solution.  
bullet A faster version computes  lengths for all puzzles by applying reverse moves from the goal position for all paths and tracking the shortest path found from each board position to the goal.       

February 18, 2016:  Version 2.0 adds user control of the target board.  A high school student learning Java (L) had a version of this puzzle in a coding competition except the goal was all coal instead of all diamonds      ([000 000 000] instead of [333 333 333]).   I also cleaned up some of the screen formats and text.    

Running/Exploring the Program 

Suggestions for Further Explorations

bullet There are 218 (262,144 = 49 = 4 choices for each of 9 locations) total boards of which 214 (16,384, or  1/16th of the total) lead to a solution.  It would be interesting to investigate the other boards.  Are there 15 additional mutually exclusive sets that all can link to each other?
bullet  In is likely that only 2048 of the 16,384 these are unique if board rotations and mirroring are considered.  It could save considerable memory and load time if each starting board was mapped into one of these 2048 boards, then solved and mapped back to the displayed solution.
  T

 

Original Date: July 13, 2006

Modified: July 29, 2017

 

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