When I was home over the holidays, one of my good high school friends got me hooked on the NYT Pips game. If you’re not familiar, it’s a puzzle game where you arrange a provided set of dominoes onto a board so that their values satisfy some constraints like “these 3 spots add to 5” or “these spots are all equal”.
While we were downhill skiing over the break, said friend and I got to discussing how you might write a solver for Pips. I thought that SMT solvers like Z3 might be a good fit, and indeed we found a couple of blog posts (one, two) solving the game that way. But we were curious about how we might write one ourselves. In particular, we wanted to know how big the solution space really was: could we just brute-force it, or were there too many possible solutions for a computer to handle?
Thinking about the number of solutions
The number of possible solutions breaks down—the way we thought about it—into two main components:
- The number of geometric arrangements of dominoes onto the board. To be valid, an assignment must fill the entire board.
- For each of those arrangements, the number of ways that the dominoes can be assigned to each space.
The second component seemed easy enough to reason about: a geometric arrangement of dominoes gives $d$ spaces to each be filled by one of the $d$ given dominoes in one of two ways (either not-flipped or flipped, ignoring doubles). There are $d!$ permutations of dominoes into the $d$ spaces, and each domino in each permutation can be either flipped or not flipped, for a total of:
$$ \text{solutions per arrangement} = d! \cdot 2^{d} $$But figuring out the number of possible geometric arrangements was too hard for us to figure out on the chairlift (even after several runs): the simple cases were easy enough but as the grid got bigger it was hard to see any pattern. So I decided I’d just write some code to figure it out for the most common cases first.
Calculating geometric arrangements
Since we were just interested in approximating the number of solutions, I thought it’d be good to first think about just rectangular boards. Though the boards for Pips are rarely rectangles, the rectangular case should be a good place to start. And on the day that I decided to do this, the hard puzzle was just a $6 \times 5$ rectangle.
To get going, I wrote some quick code to model a board, pieces on a board, and conflicts between pieces. Then I wrote a basic recursive backtracking algorithm to enumerate all possible assignments, and got the following results for $m \times n$ boards:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 2 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
| 3 | 0 | 3 | 0 | 11 | 0 | 41 | 0 | 153 |
| 4 | 1 | 5 | 11 | 36 | 95 | 281 | 781 | 2245 |
| 5 | 0 | 8 | 0 | 95 | 0 | 1183 | 0 | 14824 |
| 6 | 1 | 13 | 41 | 281 | 1183 | 6728 | 31529 | 167089 |
| 7 | 0 | 21 | 0 | 781 | 0 | 31529 | 0 | 1292697 |
| 8 | 1 | 34 | 153 | 2245 | 14824 | 167089 | 1292697 | 12988816 |
I sent this to my friend, and he pointed out that the $2 \times n$ case looks an awful lot like the Fibonacci sequence! Of course, I learned from Grant Sanderson that patterns fool ya, so I had my program compute some more $2 \times n$ arrangements:
$$\begin{array}{r|rrrrrrrrrrrrrrrrr} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & \cdots \\ \hline & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & 610 & 987 & 1597 & 2584 & \cdots \\ \end{array}$$I went up to $2 \times 36$ ($24157817$) before my computer started to really slow down, and it kept following Fibonacci.
Why Fibonacci?
At first, it seemed pretty crazy that Fibonacci would show up inside the NYT Pips. But the $2 \times n$ case is pretty simple, and the fact that the number of total arrangements for each $n$ looks like Fibonacci gives us a hint about what a good way to think about the relation: Fibonacci is defined as:
$$F(n) = F(n-1) + F(n-2)$$so let’s think about the $n - 1$ and $n - 2$ cases of a $2 \times n$ Pips board and how they each contribute to the total number of arrangements that fill a $2 \times n$ board.
Claim 1: There is exactly one way to turn a valid $2 \times (n -1)$ arrangement into a valid $2 \times n$ arrangement.
Drawing it out, it looks like for any arrangement that fills a $2 \times (n - 1)$ Pips board, we can simply add one vertical domino at the end to fill a $2 \times n$ Pips board. And indeed this is the only way to fill a $2 \times n$ Pips board given an arrangement that fills a $2 \times (n - 1)$ Pips board.
Claim 2: There is exactly one way to turn a valid $2 \times (n -2)$ arrangement into a valid $2 \times n$ arrangement that is distinct from any valid $2 \times (n - 1)$-derived arrangement.
If we think about a $2 \times (n - 2)$ Pips board, there are two ways to fill it out: we need two dominoes to fill the four empty squares, but those two dominoes can be either vertical or horizontal.
However, we are interested in counting the number of unique geometric arrangements of dominoes to fill a $2 \times n$ board. With the final dominoes in the $n-2$ case vertical, we’ve created a duplicate with the arrangements covered by the $n-1$ case: since removing the right of the two new dominoes would give a valid arrangement for a $2 \times (n -1)$ board and we already consider adding a vertical domino to every valid $n-1$ arrangement, all of those arrangements must already be covered by the $n - 1$ cases. So the only contributors to unique geometric arrangements for the $2 \times (n - 2)$ case are those with two horizontal dominoes filling the extra space.
This is sounding like Fibonacci, but one might finally wonder if we need to also consider any smaller instances of the recurrence. For example, is it possible to create any new arrangements that are derived from an arrangement that fills a $2 \times (n - 3)$ board? I claim that it is not and indeed that it is not possible for any small instance:
Claim 3: All valid $2 \times n$ arrangements must be an extension of either a valid $2 \times (n - 1)$ or a valid $2 \times (n - 2)$ arrangement.
Taking the example of $2 \times (n - 3)$ from above, filling the empty space to the right of the $2 \times (n-3)$ arrangement requires that each space is filled by a portion of either a horizontal domino or a vertical domino. Since all dominoes have dimension $1 \times 2$, it is necessary to complete either a valid $2 \times (n -1)$ or $2 \times (n -2)$ arrangement in order to complete a valid $2 \times n$ arrangement, and therefore any valid arrangement derived from a $2 \times (n -3)$ arrangement would also be included in the arrangements considered above. This applies in the same way to any smaller instance of the recurrence, so it is sufficient to count all possible arrangements to consider only the $n-1$ and $n-2$ cases.
Combining these three claims, since there is exactly one way to turn a valid $2 \times (n-1)$ arrangement into a valid $2 \times n$ arrangement and exactly one way to turn a valid $2 \times (n-2)$ arrangement into a valid $2 \times n$ arrangement, and because all valid $2 \times n$ arrangements must also be a rightward extension of either a $2 \times (n-1)$ or a $2 \times (n-2)$ arrangement, we can say that the number of possible arrangements of dominoes to fill a $2 \times n$ Pips board is equal to the sum of the number of possible arrangements to fill a $2 \times (n-1)$ board and to fill a $2 \times (n-2)$ board. If we call $F(n)$ the number of possible arrangements to fill a $2 \times n$ board, then, and set base cases of $F(1) = 1$ and $F(2) = 2$ for the $2\times 1$ and $2 \times 2$ cases, this gives:
$$ F(n) = F(n - 1) + F(n - 2)$$
Just like Fibonacci.
Nothing new
Of course, my friend and I did not discover a new field of math by playing Pips. Some Googling suggested that this problem is called Domino Tiling, and the general $m \times n$ case was solved by Temperley & Fisher and by Kasteleyn in 1961 in the context of statistical mechanics and physics, respectively, as:
$$ \prod^{\lceil\frac{m}{2}\rceil}_{j=1}\prod^{\lceil\frac{n}{2}\rceil}_{k=1} \left( 4\cos^2 \frac{\pi j}{m + 1} + 4 \cos^2 \frac{\pi k}{n + 1}\right)$$But it was a lot more fun to play around with it myself and be surprised by the Fibonacci than to read it on Wikipedia :)
So, can we brute-force it?
Fibonacci aside, the original question we set out to answer was whether the solution space of a regular Pips game was small enough for a computer to brute-force. We discovered above that the number of geometric arrangements for a standard-sized “hard” board, such as the $6 \times 5$ one from Jan. 11, contributes only a factor of a few thousand geometric arrangements ($1183 \approx 2^{10}$ in the $6 \times 5$ case). The number of dominoes $d$ and the way that they can be assigned within a geometric arrangement contributes a much larger factor: $d! \cdot 2^d$ or, for $d = 15$, $4.28 \times 10^{19} \approx 2^{55}$.
$2^{55}$ is already outside the range of brute-forcing effectively—at even a wildly unrealistic checking rate of 1 solution per CPU cycle, a 5GHz CPU ($\approx 2^{32}$ cycles/sec) it would take about $2^{23}$ seconds, or 97 days, to check every possible solution for a single geometric arrangement. Adding in the factor of $2^{10}$ for the number of geometric arrangements bumps us up to $2^{32}$ seconds, or 272 years. I think we need something smarter.