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:
 |
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.
|
|
|
Build the entire graph of 49
board
states |
|
|
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. |
|
|
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. |
|
|
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
 |
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? |
|
|
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:
May 15, 2018 |
|
