[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 simplify testing.  That turned into a few days of "fun" coding and learning about "tiling the plane" problems.   More about the technique i used 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 topleft values set to (-1,-1).

Counting Possible and User defined

To be completed ASAP

Search and Add Logic.

To be completed ASAP

Running/Exploring the Program 

Suggestions for Further Explorations

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

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