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

Problem Description

The standard set of 28 dominoes from blank/blank through 6/6  of size 1x2 units have been placed randomly on an 8x7 grid and their outlines erased.  The puzzler's task is to replace the outlines, i.e. to redraw the 28 dominoes. . 

Background & Techniques

I ran across this puzzle in one of my puzzle books, Logical Puzzles, Chartwell Books Inc., 2006.   As usual, when I'm too slow or lazy to solve a puzzle with pencil and paper, I started to think about solving it with a program.  Today's program is the result, but this version does not  even solve puzzles from the book.  After investing a week on the project, I decided it was time to publish version1 and save the complete solution for V2. 

It seemed like generating random puzzles would simplify testing.  That turned into a few days of "fun" coding and learning about "tiling the plane" problems.   More about the technique I used is in the "Programmer's Notes" section below.  Once I could generate boards, the next problems were to allow the user to "draw" domino outlines by clicking and dragging between adjacent numbers that were not already part of a domino outline.  And, of course, allowing outlines to be be erased and  displaying which dominoes had been "found".  So here are the features found in this version:

Enjoy! 

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

Programmer's Notes:

Domino Object (TDomObj)

The board is an 8x7 TStringGrid which displays a single integer from 0 to 6.  Associated with each cell is an Object  property which is used to hold additional information about this cell.  The TDomObject contains information about the user definitioon: whether this cell  is available (Orientation=' ') or has been assigned as part of a horizontal (Orientation='H') or vertical (Orientation='V') domino.  For efficiency,  The TopLeft  TPoint structure indentifies the cell coordinates of the top or left cell for this domino, the Val TPoint and  Nbr properties  give the domino dot values and the number assigned to this domino.   These fields are duplicated in a Solutionsrec record which contain information about the solution domino definitions.  Solutionsrec contains an Opengroup property which is used  when generating new puzzles as described below.   .    

Generating a random puzzle

Tiling a plane randomly with dominoes is not as easy as I though it would be.   The Wikipedia article on Domino Tiling was not very helpful.   When I tried just generating dominoes in random open cells with random orientation, after 20 or 21 were placed, there were inevitably no more places left (the rest of the squares were single cells with no open neighbors.  I finally decided to check open groups of cells  where an all of the cells that could be visited by walking to an adjoining open cell  belong to the same opengroup.   Because every domino occupies 2 cells, every opengroup must have an even number of cells.     By not placing a domino anywhere that would result in an odd parity opengroup, we can usually find a solution in fewer than 100 attempts.   It turns out that are are a few configurations of even parity opengroup which cannot be filled.  So the Generate button calls the MakeSolution which call function TryToBuild up to 10 times looking for a solution.  Each entry to TryToBuild will loop up to 1000 times to place dominoes randomly wiithout leaving any odd parity opengroups.     

Drawing Dominoes

The board grid, Stringgrid1, uses an OnDrawCell exit to display the domino dot value number.  It also uses the Objects TDomObj properties to decide if this cell is part of a domino and if so whether it should draw a U shaped partial domino opening up, down, right, or left.  When the other cell is draw the domino outline will be completed.   The TDomObj  contains a Solutions record which contains field pertaining to the solution domino definition. as well as properties which apply to the current user domino definition.  User domino outlines are always drawn in red.    If the "Show Solution: checkbox is checked,   the StringGrid1 Tag property is set to "1" which causes the DrawCell exit to draw the solution domino in black and slightly larger than any user domino definition.

Creating/Erasing outlines with the mouse

A Mouse down exit in Stringgrid1 sets a dragit flag and saves the start cell coordinates of the mouse button was pressed on a open cell.  When the mouse button is lifted, a check is made that this is a valid 2nd cell for the domino being defined.  If so, the Orientation, Topleft, and other field relative to this definition are filled in in both the start and ending cells.    If the mouse button is pressed on an existing definition, it is erased by setting orientation back to ' ' and top left values set to (-1,-1).

Addendum June 6, 2013: 

Version 2 adds a "Load predefined case" button to load case text files (and solutions) created by a new "Define Domino Arrays" program.  Several sample cases from the "Logical Puzzles" book are included. The Regenerate button now also reloads the current case file to allow starting over.

Define Domino Arrays  is new a program included with the downloaded zip files. It builds files for input to the Domino Search program. That program knows how to generate and solve randomly generated rectangular arrays containing all 28 standard dominoes (from 0 & 0 through 6 & 6 dots per domino). However it does not yet know how to solve arrays that are predefined (like those found in the book "Logical Puzzles" published by Chartwell Books Inc., 2006).

As an interim step, Define Domino Arrays knows how to find the domino outlines from an 8 x 7 array of "half domino" values entered by users. The source might be the book referenced above or from an actual physical rectangular domino arrays.  If a valid array is entered, the program can solve, and allow users to save
and reload each puzzle & solution. Files created here may be read by the Domino Search program allowing users to solve them manually, with hints, or display the full solution. Several sample arrays are incliuded with the downloads. Additional valid array can also be created by "swapping" dominoes within an existing valid array. 

The new program finds a solution using "Trial and error depth first search with backtracking". That is, for each domino it finds finds all locations within the array where that domino might reside. It then tries these locations
one at a time, proceeding from domino to domino as far as possible until all are placed or the program hits a dead-end. For dead-ends, the program removes the dominoes and tries the next candidate location "backtracking" in reverse order up the list of placed dominoes. There is an experimental "Optimized Search" which places dominoes stating with those with the fewest candidate locations. In practice, that seems not to reduce search times in most cases, although times are only a few milliseconds with or without optimization. For now, the failure to improve times remains a mystery for future study.
 

Running/Exploring the Program 

Suggestions for Further Explorations

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

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