Domino Search

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

Contact

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

Search DelphiForFun.org only

 

 

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

Unsolved

Solved

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:

  • A Generate button to make a new puzzle. 
  • A Show the Solution checkbox to display the correct domino outlines.  Only the "honor" system keeps you from using it until you give up.  This feature is well tested by me.
  • The starting random number "seed" used to generate a puzzle is displayed.   A Regenerate button will recreate a puzzle based on the current key value.  Users may note any puzzle key and reenter it later to work on the puzzle  (or to send  to me to report a bug J).
  • A second grid to display how many times each domino has been defined by the user.  The intersection of the smaller domino value across the top and the larger domino number down the side shows the value for that domino. The target  is to get 28 "1"s in the 28  domino intersections.  Zero's are dominos that haven't been found yet, counts greater than 1 are allowed in our virtual world, but cannot lead to a solution  since each domino occurs on the board exactly once.  This display is activated by the "User defined counts" option in the "Show for each domino" radio box.
  • While working on puzzles I realized that I started each puzzle by searching for domino  that could only occur in one place on the board and started by outlining those.   My philosophy is to let the computer answer all the questions I can make it answer.  As a result, I added another display option to the second grid to show the number of places where each pair of values occurs.   So the "1"'s are the dominoes that can be immediately  defined since there is only one valid  location for them.  As an enhancement, I display the counts for dominoes that have already been defined in red text.     Now we need to find the black one's dominoes to outline next.   Along the same lines, black "0"s indicate dominoes that have not been found yet and which cannot be outlined  with the currently defined  outlines.  This display is activated by the "Possible location counts" option in the "Show for each domino" radio box.
  • One final step was to add a "Search and add" button to outline all of those black "1"s dominoes.   An additional feature of this button is to add outlines for any unoccupied cells which have 3 occupied neighbors. Since every cell will be part of some domino, a cell with only one unoccupied neighboring cell must belong to the domino defined by those two cells.    

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

June 2013: Accept (and save) puzzle definitions from (to) external text  files. Now loads files created by Domino Definition program.
.June 2013: Perform complete puzzle solution search, probably recursive depth first search of board positions. Implemented in a separate Define Dominoes program.
Show "preview" domino outline as the mouse moves over candidate 2nd cells with left button pressed.
   
   

 

Original:  August 3, 2008

Modified:  February 18, 2016

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