┌───────┐
        │     = │
    ┌───┴───┬───┴───┬───┬───┬───┐
    │     6 │    12 │ 5 │   │   │
    ├───┬───┼───┬───┴───┤   │   ├───┐
    │   │   │ * │     ≠ │   │10 │ * │
┌───┘   │   ├───┼───────┤   ├───┴───┤
│    18 │   │ * │    10 │ 6 │       │
└───────┘   ├───┴───┬───┴───┤       │
            │       │       │     0 │
            │       │       ├───┬───┤
            │     4 │       │<3 │<2 │
            └───────┘       └───┴───┘

Dominoes:

0-1   0-2   1-1   1-2   1-5   2-4   3-0
3-4   3-6   4-0   4-5   5-2   6-2   6-4
6-5   6-6

Found a solution in 00:00:01.0045242:

        ┌───┬───┐
        │ 4 │ 4 │
    ┌───┤   │   ├───────┬───────┐
    │ 3 │ 3 │ 6 │ 6   5 │ 2   6 │
    │   ├───┼───┴───┬───┴───┬───┼───┐
    │ 6 │   │ 4   5 │ 4   2 │ 4 │ 3 │
┌───┴───┤   ├───┬───┼───────┤   │   │
│ 6   6 │   │ 2 │ 5 │ 5   2 │ 0 │ 0 │
└───────┘   │   │   ├───────┼───┼───┤
            │ 1 │ 1 │       │ 0 │ 0 │
            ├───┴───┤       │   │   │
            │ 1   1 │       │ 2 │ 1 │
            └───────┘       └───┴───┘

Pips is a new puzzle game from the New York Times. The object is to cover a shape made from square cells with a set of dominoes, subject to some constraints, such as that the number of pips in a region of the puzzle must sum to a specific number. The Times publishes three puzzles every day, labeled "easy", "medium", and "hard". (In fact, as of this writing, they publish the puzzle data well ahead of time, if you're willing to read JSON.)

Solving Pips is a good programming challenge because the number of possible solutions increases quickly as the board gets larger. Some of the hard-level Pips games can take a very long time to solve by a brute force search, so we'll have to be clever to get the time under, say, a few seconds in the worst case.

To solve Pips, we'll use a backtracking algorithm, which is essentially a rigorous version of "trial and error". The idea is to place one domino at a time on the board. If, after placing a domino, the resulting state of the puzzle is still valid (i.e. conforms to all the constraints), then we repeat the procedure with another domino in another location, etc. If the placement is invalid, we pick up that domino and try another one in that spot. In this way, we will eventually find all solutions to the puzzle, or we can stop after we find the first one. Most of the hard Pips puzzles have a single solution, but a few have more than 100 distinct solutions, and one has 2,764,800!

We'll use F# to implement this algorithm because functional programming is a good choice for "black box" problems like this that have no side-effects, and .NET is an easy, fast platform to work with. (F# is actually a great all-purpose language for just about anything, but I digress.)

In order to speed up the search for solutions, we'll make two improvements over vanilla backtracking:

• Use geometric information about possible tilings to guide the search.
• Prune the search tree aggressively to avoid investigating dead ends.

More on both of these enhancements below.

One key observation is that there are only so many ways to tile a given shape with dominoes. For example, there are just three ways to tile a 2×3 rectangle:

┌───┬───┬───┐      ┌───┬───────┐      ┌───────┬───┐
│ ■ │ ■ │ ■ │      │ ■ │ ■   ■ │      │ ■   ■ │ ■ │
│   │   │   │      │   ├───────┤      ├───────┤   │
│ ■ │ ■ │ ■ │      │ ■ │ ■   ■ │      │ ■   ■ │ ■ │
└───┴───┴───┘      └───┴───────┘      └───────┴───┘

So a tiling that starts off like this:

┌───┬───────┐
│   │ ■   ■ │
├───┴───┬───┤
│ ■   ■ │   │
└───────┴───┘

is bound to fail because we've left two unconnected 1x1 areas, and there's no way to tile an odd number of cells with dominoes.

We can use this knowledge to reduce the number of configurations we have to examine when searching for Pips solutions. For example, if we start by placing a domino horizontally in the top-left corner of the 2×3 rectangle, we know where the other two dominoes have to go:

┌───────┬───┐     ┌───────┬───┐
│ ■   ■ │   │     │ ■   ■ │ ■ │
├───────┘   │  →  ├───────┤   │ 
│           │     │ ■   ■ │ ■ │
└───────────┘     └───────┴───┘

To guide our backtracking algorithm, we can organize the tilings of a given shape into a "forest" of trees. Each node in a tree shows the placement of a domino in the tiling, and its child nodes show how the rest of the dominoes are placed, until we get each of the complete tilings as leaf nodes. For example, here are the five distinct tilings of a 2x4 rectangle arranged step-by-step in trees:

(Side note: Gemini is quite good at generating SVG images, if you coax it along. But PNGs, not so much.)

With this in mind, our backtracking algorithm is:

• Given: A Pips puzzle in some state of completion, and a collection of tiling trees that indicate where the next domino might be placed.
• If there are no more dominoes to place, the puzzle is solved.
• Otherwise, for each given tiling tree:
  • Get the next domino location from the root of the tree.
  • Try placing each remaining domino in that location. If that is a valid placement, recursively apply the algorithm to the child trees. (Don't forget to try placing the domino in both orientations, if it is not a double.)

If we wait until all dominoes have been placed to check whether the constraints of the puzzle have been met, it can take too long to find a solution. Instead, we aggressively check the constraints as we go along, and backtrack as soon as we know that a solution isn't possible along the current path. This process is called "pruning" the search tree.

Note that placing a domino in one region of the puzzle can affect the validity of another region, because dominoes can't be used twice. This means that we have to check the validity of all the regions of the puzzle after each domino is placed.

All cells in an "equal" region must have the same value, although the value itself is not specified by the constraint. We use two rules to validate these regions:

1. The number of distinct pip counts in the region cannot exceed one.

2. There must be enough matching values available among the remaining dominoes to fill the region, For example, if the region has four cells, and one of them is covered by a domino with 2 pips on that side, are there at least three more domino sides with 2 pips among the remaining dominoes?

All cell values in an "unequal" region must be different. Again, we use two rules to validate these regions:

1. The number of distinct pip counts in the region cannot be less than the number of filled cells.

2. There must be enough distinct values available among the remaining dominoes to fill the region.

The sum of all cell values in this type of region must be less than the specified target. There are two ways to validate these regions:

1. The sum of all filled cells in the region must always be less than the specified target.

2. There must be enough small values available among the remaining dominoes to fill the region without exceeding the target. For example, if a values in a three-cell region must sum to less than 15, and two of the cells are already filled with 5 and 6 pips, then there must be at least one domino side with 3 or fewer pips among the unused dominoes.

The sum of all cell values in this type of region must be greater than the specified target. In this case, we can't invalidate the region just because the filled cells don't yet exceed the target. However, we can still prune the search tree using this rule:

1. There must be enough large values available among the remaining dominoes to fill the region and exceed the target.

The sum of all cell values in this type of region must equal the specified target. This is the most complex region type to validate, because we have to consider both upper and lower bounds:

1. The sum of all cell values in the region must never exceed the target. (Assuming there are no negative pip counts!)

2. If the region is completely filled, the sum must equal the target.

3. Otherwise, there must be enough small values among the remaining dominoes to fill the region without exceeding the target, and there must also be enough large values among them to reach the target.

4. Lastly, we can use a knapsack algorithm to determine whether it is possible to reach the specified sum with the remaining dominoes. This is an expensive check, so we only perform it if the other checks pass.

As of this writing, there have been 88 hard Pips puzzles published by the New York Times, from August 18 to November 13, 2025. Using the above algorithm, I was able to find a solution to all of them in a total of about 1.8 seconds on my development machine (a Dell XPS with an Intel i9-12900 CPU). The hardest by far was the elephant-shaped puzzle from October 14 (top illustration), which took just over one second to solve.

Finding all the solutions to each puzzle took longer, especially for the monster from September 15, which took 130 seconds:

We're finally ready to turn these ideas into code!

True to the name of the game, the dots on a domino are called "pips", and each side of a domino has between 0 and 6 pips. For example, this is the 6-5 domino:

┌───────┬───────┐
│ o o o │ o   o │
│       │   o   │
│ o o o │ o   o │
└───────┴───────┘

The corresponding F# types:

/// Number of pips on one side of a domino.
type PipCount = int

/// The two sides of a domino.
type Domino =
    {
        /// Left side of the domino.
        Left : PipCount

        /// Right side of the domino.
        Right : PipCount
    }

The code actually makes no assumption that 6 is the largest pip count on a domino, although this is the convention in all NY Times puzzles.

A domino is a "double" if the pip count is the same on both sides:

module Domino =

    /// Is the given domino a "double", such as 6-6?
    let isDouble domino =
        domino.Left = domino.Right

Doubles are special because they only have one distinct orientation, while other dominoes have two.

Note that, according to this definition, the 6-4 domino is different from the 4-6 domino. We could implement custom equality and comparison to make them equal, but it would slow down the solver for little benefit. By convention, there are no duplicate dominoes in a Pips puzzle, so checking for them is not necessary.

Each cell on the board has (row, column) coordinates:

/// A cell in a grid.
type Cell =
    {
        /// Row coordinate (0-based).
        Row : int

        /// Column coordinate (0-based).
        Column : int
    }

And in order to place dominoes correctly, we need to define what it means for two cells to be adjacent:

module Cell =

    /// Gets all possible cells adjacent to the given cell.
    /// Some of these cells might not actually exist, though.
    let getAdjacent cell =
        [|
            { cell with Row = cell.Row - 1 }
            { cell with Row = cell.Row + 1 }
            { cell with Column = cell.Column - 1 }
            { cell with Column = cell.Column + 1 }
        |]

A pair of adjacent cells is an "edge" (in the graph theory sense):

/// A pair of adjacent cells.
type Edge = Cell * Cell

When we place a domino on an edge, the left side of the domino always goes on the first cell in the edge, and the right side of the domino goes on the second cell. To get both possible orientations (assuming the domino is not a double), we could either flip the domino around or reverse the cells in the edge. We choose the latter convention in order to avoid changing a puzzle's dominoes:

module Edge =

    /// Reverses the given edge.
    let reverse ((cellA, cellB) : Edge) : Edge =
        cellB, cellA

A board is a rectangular grid on which dominoes are placed. In addition to storing the location of each domino, we also need a quick way to look up the value at any cell on the board:

type Board =
    {
        /// Location of each domino placed on the board.
        DominoPlaces : List<Domino * Edge>

        /// Value in each cell.
        Cells : PipCount[(*row*), (*column*)]
    }

We store a special pip count of -1 in the array to indicate an empty cell, and copy the entire array every time we place a domino on the board in order to maintain immutability:

module Board =

    /// Places the given domino in the given location on the
    /// board.
    let place domino ((cellLeft, cellRight) as edge : Edge) board =

            // copy on write
        let cells = Array2D.copy board.Cells
        cells[cellLeft.Row, cellLeft.Column] <- domino.Left
        cells[cellRight.Row, cellRight.Column] <- domino.Right

        {
            Cells = cells
            DominoPlaces =
                (domino, edge) :: board.DominoPlaces
        }

Regions tell us where we are allowed to place dominoes on a board and impose constraints that must be met by those dominoes:

/// A region of cells on a board.
type Region =
    {
        /// Cells in the region.
        Cells : Cell[]

        /// Constraint on the cells in the region.
        Type : RegionType
    }

A tiling is a set of edges:

And we need a way to obtain all possible tilings for a given shape, as defined by a set of cells:

module Tiling =

    /// Gets all tilings for the given set of cells.
    let getAll (cells : Set<Cell>) : Tiling[] =
        ...   // implementation omitted for brevity

A Pips puzzle contains:

• A set of unplaced dominoes
• An array of regions
• A board of cells, some of which may be covered with dominoes

When a puzzle is created, the board is empty. When it is solved, all the cells in the puzzle's regions are covered by dominoes, and the set of unplaced dominoes is empty. The initial puzzle, its solution, and all the states in between are represented by the same type:

/// A Pips puzzle in some state of being solved.
type Puzzle =
    {
        /// Available dominoes that have not yet been placed
        /// on the board.
        UnplacedDominoes : Set<Domino>   // assume no duplicates

        /// Regions of cells that impose constraints on the
        /// dominoes placed there.
        Regions : Region[]

        /// A board of cells, some of which may be covered
        /// with dominoes.
        Board : Board
    }

We can use our backtracking algorithm to find the solutions to a Pips puzzle:

module Backtrack =

    /// Finds all solutions for the given puzzle by back-
    /// tracking lazily.
    let solve (puzzle : Puzzle) : seq<Puzzle> =
        ...   // implementation omitted for brevity

The backtracker is lazy, so the caller can stop after finding the first solution, if desired.