This article develops and compares three methods for solving domino grid puzzles: a “human-type” algorithm, a brute-force method, and a scheme using a generalized odometer.

A Puzzle Is Presented, and a “Human-Type” Solution Algorithm Developed

When my son brought home a paper from school with a grid of numbers on it, I was immediately interested. The goal: cover the puzzle with all the dominoes from the “bone pile,” making sure that each number of the puzzle is covered by the same number on a domino. Many similar puzzles can be found online and in puzzle collections: see [1, 2, 3, 4, 5] for several online resources, which are the source of some of the examples considered here.

Figure 1. A partially solved domino grid, with almost half of the 28 dominoes placed on the underlying puzzle grid.

Puzzle Construction

Board

Our first task is to represent the board.

Bone Pile

Next, we need the bone pile, the list of available dominoes. In this case, the bone pile consists of all 28 dominoes from the double zero to double six, but the definition is generally valid for any non-negative number , for a total of dominoes.

Locations

Find possible locations for a given piece .

This is the workhorse of the entire solution, first dividing the puzzle into pairs along each row and looking for matches to the given pair, then repeating the process on the transposed matrix (i.e. along the columns of the original grid) and noting the locations of any matches found. The location of the pair in the partition gives the location of the first half domino in the original grid, but adding the appropriate offset gives the location of the second half domino as well, and both are included as a domino location in the list of locations found.

Displaying Dominoes

Now for functions to highlight the dominoes within a puzzle. The function frameDomino generates the options to include in the Frame option of Grid.

The function displayPuzzle accepts a puzzle grid (a matrix) and a domino list (a list of location pairs) and displays the puzzle grid with frames around the dominoes indicated in the list.

For example, there are two possible locations for the domino in the m9 puzzle.

A puzzle object takes three arguments.

1. The matrix m contains the puzzle to be solved, a 2D array of integers.
2. The filled locations list filled is a list of coordinate pairs: , where either and or and .
3. The bone pile bones, the list of unplayed dominoes, consists of a list of pairs of integers.

The Format command defines how to format a puzzle: the puzzle matrix has its filled list of dominoes framed, and a tooltip shows the bone pile, if any.

Initial Puzzle

This section shows examples of various puzzles; mouse over a puzzle to see the bone pile. In this puzzle, no dominoes have been played yet.

Here two pieces have been removed from the bone pile and placed on the board.

Solution Tools

Hide Board Positions Already Filled

To ensure that the squares filled by already placed pieces are no longer included, make a version of the board with the affected squares blanked out.

Forced Locations

This function finds the forced locations; only one piece can possibly go into a forced location.

Find the forced locations after two particular dominoes have been played.

The forced locations are shown empty.

Solution Method

1. Select the pieces that fit in forced locations.

• If there are any squares where no pieces can be placed, the puzzle is unsolvable, so quit.
2. Use find to return a list of all possible locations for playable pieces, and select the pieces that have only one possible location:

• If any piece has no possible placement, the puzzle is unsolvable, so quit.

• If all the pieces have multiple possible locations, take the first piece with the minimum number of locations, and do all options on duplicate boards.

Examples

In this artificial case, there are two forced locations: in each, only one piece can be placed.

The function step finds the forced locations and fills them in with the appropriate dominoes taken from the bone pile. Mouse over to see that these dominoes have been removed from the bone pile.

At the beginning, there are no forced locations, but there are four forced pieces: pieces that can only be placed in one location in the puzzle: , , , and . The step function plays all four at once.

Solve It!

We are ready to solve the whole puzzle. The next command prints the current state, takes one step, and repeats until the bone pile is empty.

Along the way, multiple partial solutions had to be considered when no forced locations or forced pieces were found, but in the end all but one solution were dropped because of inconsistency. The comments were left in to show the forced locations or forced pieces at each step, but now we turn them off.

Alternative Display Function

There is no reason not to make a prettier display function to show the dominoes with their customary pips (or dots), rather than showing only the grid numbers. We can represent the pip positions by matrices, some of which can be easily created by built-in matrix commands. Since the pip positions of double-9 and double-6 domino sets are consistent, let us build the larger set here. (A double-12 set would require adjusting the pip positions.)

The other matrices could be built by hand or using SparseArray or Table with appropriate criteria, but it is easy to create them by addition and subtraction.

A pip will be placed on a half-domino square wherever the matrix had a 1.

The function displayDottedPuzzle creates a graphical display of the puzzle, optionally replacing numbers by half-domino faces for any locations listed in the “filled list,” outlining any placed dominoes in a way similar to displayPuzzle.

Animate the Solution

Thoughts

The method described here can be thought of as “human-type,” since it uses intelligently chosen criteria for deciding which step to perform and which option to try next. The criteria used can be summarized as follows:

1. Seek forced locations: if any locations can take none of the available dominoes, abandon the partial solution currently being constructed; if any locations can take exactly one available domino (and not the same one), fill all of these “forced locations.”
2. Else seek forced dominoes: if any of the available dominoes cannot be placed on the board, abandon the partial solution currently being constructed; if any of the available dominoes can only be placed in one location on the board, play all of these “forced dominoes.”
3. Else for a minimal case, place one domino in all possible locations, making separate copies of the puzzle for each case.
4. Repeat until no further changes occur.

A human can make more complicated arguments eliminating some options; for examples, see the explanations at the sites [1, 2, 3, 4, 5]. (But not all suggested solving strategies turn out to be useful. One common idea, placing the “double” dominoes first, can easily be defeated by a clever puzzle designer.) The order is arbitrary and might be modified, but is far faster than the more simplistic, brute-force method presented in the following section.

Brute-Force Collision Method

Here is a list of all possible locations of all dominoes in our original puzzle.

The number of options for the pieces varies wildly.

(You can easily verify that in this puzzle, all the double dominoes have between four and eight possible placement options, making “place doubles first” a poor strategy in this case.) Taking all possible options for all the pieces gives a very large number.

Too many cases to consider! But this method would work, theoretically: Use Outer to get all combinations of choices of these options and then use Select on those that have no overlapping dominoes. Here do only the first three dominoes.

Using the first three dominoes, there are possibilities, reduced to 19 after elimination of conflicts. Placing the first 13 dominoes involves considering 653184 cases, of which only four have no conflicts.

So the following code should work, but will take an unreasonable amount of time and memory. It is beautifully simple and short, but do not run it, as it probably would not finish in our lifetimes!

Odometer Method

“To a hammer, everything looks like a nail.” A few years ago, I worked out an exhaustive search-and-collision detection algorithm based on a idea of a generalized odometer, and since then I have seen applications for it everywhere. It works here, too.

Method

Create a 28-digit generalized odometer, whose digit refers to which option we are trying for the domino. All digits start as 1; incrementing the odometer does not in general occur at the right end, but at the first digit (from the left) whose domino placement conflicts with that of any previous domino. A digit “rolls over” when it is incremented past its maximum value and must be reset to 1. Whenever a digit rolls over, also increment the digit to its left, just as in a real odometer. Each odometer digit has a separate maximum determined by the number of options available for that domino. When the first digit finally rolls over, all solutions have been found. We also accelerate the procedure by sorting the domino option list in increasing length.

Notice that the first four odometer digits can only be 1; each starts at 1 and has a maximum of 1.

To see or use the parts of options specified by the odometer, we use the function MapThread.

Here is the program that more or less immediately returns the answer(s).

As expected, there is only one odometer reading that works; that is, only one choice of domino placements solves the puzzle. The generalized odometer method works best for situations with a large number of variables taking on values that can be calculated in advance, particularly if the possible values are the same for all variables or vary in a way that can be easily specified. Here the options have to be recomputed for each new puzzle, making it less efficient than the previous method.

Solving Other Boards

Quadrilles

A “quadrilles” puzzle [5], an idea credited to French mathematician Edouard Lucas, can be divided into blocks, each containing the same number. Since the following figure does not completely fill a rectangular array, we add empty strings.

This particular quadrille has only one solution. At each step there are a large number of forced locations or pieces, and all 28 dominoes are placed in only four iterations.

A “Too-Easy” Puzzle

Now for a puzzle with so many different ways to solve it that one feels that almost anything will work [5]!

A Puzzle with a Hole in the Middle

If a puzzle is nonrectangular or has intentional gaps in it, such as the one shown below [4], simply embed it in a larger rectangle, and indicate the gaps by empty strings.

Last Thoughts

It seems likely that the online or downloadable domino puzzle generators effectively lay out the dominoes to create a grid that is guaranteed to be solvable. But even if all puzzles presented can be solved, a number of questions spring to mind:

For given grid dimensions, how many different solutions are there? (The three methods derived above solve individual puzzles, but what if the numbers are rearranged in a given grid in all possible ways?)

For given grid dimensions, what fraction of the possible puzzles has only one solution, and in general, for all , what fraction of the puzzles has solutions? What is the largest number of solutions possible?

Bear in mind that in the sense of the functions developed here, a “solution” is a merely a list of domino locations, so different puzzles of the same dimensions can have the same solution just by permuting the underlying grid numbers or rearranging them in other valid ways. In the interest of increased clarity, define a solution schema as a layout of dominoes face-down on a board. Now we can talk about the number of possible distinct schemas for a given puzzle grid.

What about writing a program that generates all solution schemas for a given board, ignoring the numbers? This could be done by modifying either the function solvePuzzle or the function odometerSolve, neither of which can quite do the job as written. (Yes, I did try them on a board filled with 0 entries, but they would need to be tweaked to expect a bone pile of double-zero dominoes.)

Finally, it is interesting that the first solution method worked so well, basically following how a human would decide which domino to play next. The code for the brute-force method is the simplest, but impractical without massive parallel processing. The odometer method works well, but here not as fast as the “human” method, and in any case may not be as transparent to the reader. There is more than one way to solve a puzzle! And if you spend much time thinking about a puzzle, other methods and other questions will probably occur to you.

Acknowledgments

I thank my colleagues at Southern Adventist University who have encouraged me, the folks at Wolfram Research who have occasionally helped me, and Claryce, who has put up with me in all my most puzzling moods.

References

[1]	E. W. Weisstein. “Domino Tiling” from Wolfram MathWorld—A Wolfram Web Resource. mathworld.wolfram.com/DominoTiling.html.
[2]	Domino-Games.com. “Domino Puzzles.” (Sep 4, 2014) www.domino-games.com/domino-puzzles.html.
[3]	“Dominosa.” (Sep 4, 2014) www.puzzle-dominosa.com.
[4]	Yoogi Games. “Domino Puzzle Puzzles.” (Sep 4, 2014) syndicate.yoogi.com/domino.
[5]	J. Köller. “Domino Puzzles.” (Sep 4, 2014) www.mathematische-basteleien.de/dominos.htm.
K. E. Caviness, “Three Ways to Solve Domino Grids,” The Mathematica Journal, 2014. dx.doi.org/doi:10.3888/tmj.16-10.

About the Author

Ken Caviness teaches at Southern Adventist University, a liberal arts university near Chattanooga. Since obtaining a Ph.D. in physics (relativity and nuclear physics) from the University of Massachusetts Lowell, he has taught math and physics in Rwanda, Texas, and Tennessee. His interests include both computer and human languages (including Esperanto), and he has used Mathematica since Version 1, both professionally and recreationally.

Kenneth E. Caviness
Department of Physics & Engineering
Southern Adventist University
PO Box 370
Collegedale, TN 37315-0370
caviness@southern.edu