Solving pips using Dancing Links

I wrote a solver for the New York Times’ pips puzzle. In this post I’ll explain how it works.

To my knowledge it’s the fastest solver for this problem (later in the post I’ll show benchmarks). It works by reducing pips to a form of the Exact Cover problem, then solving the Exact Cover instance. The solver is structured like a compiler: a frontend, optimization passes, an IR, and some backends. The speed comes from two sources: a new algorithm that generalizes Knuth’s Algorithm M for Exact Cover with Colors and Multiplicities (MCC); and a number of pips-specific optimization passes before the reduction.

Personal notes

I’m proud of this work because in Vol. 4B of TAOCP, Knuth suggested that someone should do exactly this generalization: extend MCC so items in options can have weights. It’s cool to imagine that at some point the thought of doing this generalization passed through his head. As the figures below will show, the new weighted MCC, which I’ve been calling mccw, has a massive effect on the solver’s performance.

Another reason I’m fond of this project is that I did all the work without any LLM involvement. I came up with ideas, read textbooks and papers, wrote all the code, ran benchmarks, fixed bugs, all that good stuff. Getting mccw to work pushed me to the very edge of my ability. It’s in the top 10 hardest-I’ve-ever-thought times in my life. These days, I’m not sure I would have done it that way. The problem is self-contained and totally verifiable. It’s basically pure math in the well-explored field of combinatorial optimization. It’s ideal for LLMs. I love that I have powerful tools now, but I’m glad I got to do this before this kind of work becomes a dead art.

(I did use LLMs for making the figures and other frontend stuff in this post.)

This post is my homage to Knuth and the kind of work he obviously loves so much. Thank you Professor Knuth!

The puzzle

Pips is a puzzle where you place dominoes on a board. Not every tiling is allowed: some regions of the board have constraints on what can go inside them. If you’ve never played it before, try today’s easy puzzle at the New York Times. Here’s the hard puzzle from Oct 28, 2025:

Some puzzles have exactly one solution while others can have millions. Here are the five hardest puzzles. We’ll see them in many of the benchmarks and charts below:

Here are all 87 puzzles considered here. Since I did this work there have been more puzzles; I haven’t studied them carefully so I left them out of this post.

Warmup: domino tilings as bipartite matching

The general class of problems in this post is tiling problems. We’re trying to cover some 2D region with domino-shaped tiles, plus maybe some extra rules. Watch for similarities between these tiling problems as we work our way up to Pips.

This warmup section is to get you thinking about tiling problems, and how to solve them by turning them into other problems that might look totally unrelated. That’s how my solver works: by reducing Pips to Exact Cover.

Warmup to warmup: tiling chessboards

Pips is complicated and its reduction to Exact Cover is really complicated, so let’s solve a simpler puzzle by reducing to a simpler problem.

The puzzle is: can we tile a chessboard with dominoes?

Now let’s cut off two opposite corners of the board. Can we tile this mutilated chessboard with dominoes?

The mutilated chessboard is a famous puzzle with an elegant solution. If you’ve never seen it before, I apologize for spoiling it for you. Here’s the solution:

Proof by figure! Here are words: no tiling of the mutilated chessboard exists, because every domino we place reduces the number of white and black squares by exactly one each. So in the end we’ll be left with two extra white squares.

Tiling more general 2D regions

Here’s a harder puzzle! Which boards can be tiled with dominoes? For example, what about this one? And if you found this one easy, what if it were a thousand times bigger, so you can’t just solve it by inspection?

The board above cannot be tiled with dominoes, but the black-white coloring-counting argument from before is not powerful enough to prove it. Instead, we can reduce this problem to bipartite matching.

To solve this problem, first color the squares black and white like a chessboard. Next, create a graph with a node for each cell and an edge between neighboring cells. “Neighbor” excludes diagonal neighbors. So every edge corresponds to a possible domino placement.

The graph we get is a bipartite graph. A bipartite graph is one with two sets of nodes (here, black and white), where edges only go between these sets, never within. Our graph is bipartite because in 2D square grid boards, every neighbor of a black square is white, and vice-versa.

Finally, find a perfect matching on this graph. Skip the next section if you know what that means.

If there’s no perfect matching, the region can’t be tiled with dominoes.

Here’s a graph where a tiling is possible, and bipartite matching finds it:

Every tiling corresponds to a perfect matching in the associated graph, and every perfect matching to a domino tiling. So we can count the number of domino tilings by counting perfect matchings in the associated graph.

This section was warmup for how the actual pips solver works. Its purpose was to get you thinking about tiling problems and reductions. Pips is harder than plain domino tiling, so we can’t expect to reduce it to a problem as easy as bipartite matching. In fact, we won’t reduce it to a graph problem at all! But the overall shape is similar: reduce to some other problem, use powerful fast algorithms for the other problem, and transfer the solution back.

Just for fun, here’s the bipartite graph for the mutilated chessboard. It’s obvious that it can’t have a perfect matching because there are two extra white nodes!

Exact Cover

As a reminder, my pips solver works by reducing Pips to Exact Cover. This section is about Exact Cover, the problem we’re reducing to.

In the Exact Cover problem there are constraints and options. Each option consists of one or more constraints. The goal is to select a set of options such that each constraint is in exactly one of the options.

We can write this as a 2D matrix of ones and zeros. The job is to select options such that every column sums to exactly one. Here, have a go at it:

Why is that useful? It turns out that many, many problems can be put in this form. Suppose that there are two roommates and three chores. Ana could do dishes and trash, but then she wouldn’t have time for laundry (row 1 below). Or she could do just the laundry (row 2). Et cetera.

The constraints are: every roommate must be assigned exactly one chore schedule (first two columns), and every chore must be assigned to someone (columns 3-5). Try solving this problem:

You may have noticed yourself doing a bit of trial-and-error. At some level, every algorithm for Exact Cover works by trial-and-error. There are clever ways to reduce the work, maybe by making the bookkeeping easier or choosing a better order in which to do the trials. It can get very sophisticated, but never forget that it’s fancy trial-and-error. (And unless P=NP, in some sense it has to be.)

You may also have noticed that someone needs to take the trash out, but there’s only one row that does it. So row 1 must be in the solution. That means row 2 can’t be in the solution, since that would double-select Ana. And row 4 can’t be in the solution, since that would double-assign dishes. So row 3 it is.

In the following demo, selecting any row will grey out conflicting rows. Try it and see how much easier it is to solve the problem:

In this problem, this completely removes any need for trial-and-error! Row 1 is necessary because trash must be taken out, then only row 3 remains, and boom we’re done.

This greying-out of conflicting rows is the essence of what Knuth’s various Dancing Links algorithms do, and also what my Weighted MCC solver does. It’s all just fancy versions of this same trick, implemented very cleverly so that undoing a branch of trial-and-error can be done really efficiently. If you’ve struggled to understand the Dancing Links paper before, maybe this framing will help.

Reducing pips to Exact Cover

Warmup: domino tilings as Exact Cover

Let’s take the domino tiling problem from before and turn it into Exact Cover instead of bipartite matching. I think a demo will be better than words:

Notice that if the board were bigger, this problem would get bigger. More columns, since each column represents a cell in the board. And more rows, since each row is a way to place a domino on the board.

Distinguished dominoes

So far, every domino has been exactly identical. Nameless, faceless, pipsless. Now let’s distinguish each domino from the others. Once a domino has been placed in one place, it can’t be placed somewhere else. That’s really easy to represent using Exact Cover! Just have one column for each domino. Here, play this demo and you’ll see:

Whoa that’s so many rows! The number of columns only grew by three, to ensure each domino gets used exactly once. But every domino now needs its own copy of all the cells to represent the option of placing that domino in that place.

Also, it’s really hard to play the game now without checking the “grey out conflicting rows” box.

Finally, Pips

We’ll turn this pips puzzle into Exact Cover. First, take a minute to think about how you’d solve this puzzle, just as a human.

Next, think about how we could turn this into Exact Cover.

Okay. While pips can be turned into vanilla Exact Cover, it’s pretty complicated and turns out to be slow to solve in practice (because it produces enormous numbers of rows).

Instead, I’m going to present Weighted Exact Cover, my generalization of Exact Cover with Multiplicities. The differences from ordinary Exact Cover are:

1. Each column must now sum to some number, called a target, instead of always having to sum to 1. (This form is studied by Knuth in TAOCP 4B).
2. Each row can have some non-negative integer, called a weight, in a column instead of always having 0 or 1. (This is my generalization.)

I need thing 1 to represent regions: the pips in a region need to sum to a given amount.

I need thing 2 to represent that when a domino is placed, putting half of it in a cell, it contributes all the pips in that half to that region.

Again, there are ways to do this without introducing weights, but encoding it involves a lot of additional rows and columns that ultimately make it slower for the solver to make progress because it can’t natively “see” the real problem.

Play with this demo to get familiar with Weighted Exact Cover!

Okay lol NOW finally actually Pips

Finally! Try playing with this demo to see how pips gets represented as Weighted Exact Cover. There are a LOT of rows, so the checkbox now hides conflicting rows instead of greying them out.

If you played with “hide conflicting rows” checked, you may have done a bit of trial-and-error, but it probably wasn’t much. This is essentially how my pips solver works. First it turns pips into Weighted Exact Cover. Then it tries picking an option and hides all conflicting options. It keeps doing that until it runs into a dead end or finds a solution, then it backtracks to the last time it made a choice and tries the next possible choice. That’s it!

Oh wait no there’s more oops. First, you might be wondering how those equals regions are handled. Those are done with what’s known as color constraints. Knuth writes about them and my mccw solver supports them.

Also, there are a bunch of optimization passes to cut down the number of options before handing the problem to the solver. That’s what the next few sections are about.

Computer do less work

When any real pips puzzle is turned into Exact Cover, it’s a lot of constraints and a lot of options. When a backtracking solver has to deal with all those options it takes a long time and a lot of nodes in the search tree. So I spent a lot of time trying to reduce the number of options by thinking about the rules of pips. Over the course of three weeks, here’s the number of search nodes that the solver needed to explore for the Elephant from 2025-10-14:

That was a log plot. Here’s the same search tree drawn as a branching tree so you can see how much less work the solver has to do. In blue is the path that finally led to a solution:

Please look at it one more time, now overlaid:

Here’s what the Exact Cover file looks like for a small pips puzzle. It was 142 lines at the start, and 7 lines by the end:

Here’s the Exact Cover instance for a harder, more interesting pips puzzle. It went from about 2000 lines to 500. There’s still plenty left for the solver to do.

The single biggest reduction in puzzle size came after I introduced the Weighted Exact Cover form of the problem (those are the columns labeled “weights” above). Before that, representing sum regions required a complex encoding that added a lot of columns and rows. You can see it quite easily. In these minimap figures, the impact of weights is visible from space.

Optimization passes

Here’s the solver as a compiler:

This section is about optimizations that are specific to pips. Each optimization tries to prove that certain options can’t possibly be in a valid solution, so it’s safe to get rid of them. The optimizations are worth it because in the worst case, a backtracking solver for an NP-Hard problem spends time exponential in the size of the problem. So reducing options could have a potentially exponential impact on speed.

Typical puzzle (geometric mean of 84)

search nodes

1. 104K
2. 29.4K
3. 20.7K
4. 1.01K
5. 979
6. 903

time

1. 232 msoriginal
2. 68.9 mszero, unequal
3. 48.7 msequal
4. 5.69 mssum
5. 5.73 msresidual
6. 5.44 msodd

Reject non-zero pips in zero regions

This is a pretty obvious rule. Humans do this without thinking: they won’t even try a placement like the one on the right. It’s obviously wrong.

Reject equal pips in unequal regions

This one is also obvious. Humans do it without thinking.

Reject unequal pips in equal regions

Another obvious one.

But the next one is finally interesting:

This rule makes sense to most humans but sometimes I’ll violate it while playing. I’ll realize I put a 3 in an equals region, but there aren’t enough remaining 3’s to fill up that region.

Reject placements that immediately violate sum bounds

Humans also mostly do this without thinking.

But now look at this rule. The idea is, suppose we have a sum region and we place a domino, which reduces the sum region’s total. Now we have to fill that total using the remaining dominoes, and only the cells left in the region. Is that possible?

There’s two ways it could be impossible:

1. If the remaining total is small but the remaining dominoes are too big.
2. If the remaining total is big but the remaining dominoes are too small.

In the code, we sort the pips of every domino except the one being placed. Then we look at the biggest and smallest N, where N is the remaining size of the region.

I was proud of this one because it’s kinda cool and it made an absolutely massive difference in performance.

I’ve never seen a human reason like this. I suppose it’s possible, but the bookkeeping would be tedious. But in code it’s trivial.

Residual sum bounds

This next one is even more fun and it builds on the last idea. In fact, it’s exactly the same as the rule above, just applied to the leftover region after removing all sum regions.

In this example, the total sum of all pips on our dominoes is 13. The two sum regions add up to exactly 9. So the pips in the remainder of the board must add up to 4. In other words, we can imagine that there’s another implied sum region whose sum is 4.

Humans don’t do this one either I think.

Inequality regions

The sum bounds rule can be extended to less-than and greater-than regions. It works pretty well and in the obvious way, so I won’t bother explaining.

Odd region rejection

This is a much less fancy version of the bipartite matching argument above. If a domino placement would result in cutting off a part of the board and leaving it with an odd number of cells, there’s no way to tile it. We can immediately reject that placement.

Computer go fast

This section is about my solver’s performance: over time as I worked on it; against other solvers; and against other methods of solving Exact Cover.

Performance improved as I worked on it

Over about three weeks and 20+ optimizations, my pips solver got about 10,000 times faster, from 7+ hours to 2.7 seconds to solve all 87 puzzles. A few ideas gave huge improvements early on. After that each idea made a smaller difference, but together they added up to a real win. Most of my effort was aimed at the five hardest puzzles because they dominate total runtime.

The 7+ hour number is for the first program I wrote that correctly solved pips end-to-end. By the time I had that down to 2.7 seconds, it was an entire multi-stage pipeline that looks like a mini-compiler.

Here’s a graph showing performance improving with every idea:

(The x-axis on these graphs is the date as I made improvements to the solver, not the date on which a puzzle was released.)

The vertical (runtime) axis on the plot above is logarithmic, which makes it look like there wasn’t much total improvement. On a linear plot you can see how dramatic a 10,000x speedup is:

Other pips solvers

Here’s a comparison with the fastest other solver, which works in a totally different way. Before I show you the numbers, here’s a picture of a particularly difficult puzzle, The Elephant, from Oct 14, 2025:

Here’s the table:

Thank you Brian Berns for publishing your solver results! One of the ways I tested my solver was to see if it matched Brian’s results, in particular the solution counts.

Weighted Exact Cover backends

All numbers earlier in this post are measured using my new mccw. But that’s not the only way to solve Exact Cover. For example, it’s possible to use Z3 to write a solver for Exact Cover and its variants, including Weighted Exact Cover. We can take the whole pips solving pipeline and switch out the very last step, and we’d still have a working pips solver.

I wanted to do my due diligence and make sure that mccw beats all of the other ways I could think of.

So I wrote five different backends to solve the Exact Cover problems that pips turns into. Here’s how they compare:

mccw.py is my prototype Python solver for the Weighted Exact Cover problem. I wrote it to make sure the idea worked and to debug the C++ version. mcc is the initial C++ solver that I modified to add weights. mccw is my final C++ solver with weights.

I wrote solvers for Weighted Exact Cover using the Z3 and CP-SAT libraries. These libraries are really fast and well-engineered. They’re a good baseline to compare to; a custom solver should do better than just throwing it to an off-the-shelf solver. Both libraries are optimized for finding a solution rather than all solutions, so the third benchmark above (time to first solution) is the fairest comparison.

Bye

This post is way too long already, so I want to give you the smallest hint for how mccw works. It modifies Knuth’s MCC, which tracks how much each column’s target has left to go. When we select an option with a weight, instead of adding 1 we add the weight to that gauge. This sounds simple, but it breaks a lot of assumptions in MCC’s control-flow. So all the work is in figuring out what breaks, what new assumptions to make instead, and how to maintain those invariants. For the rest, see the code.

One thing I’m proud of is that just like a good 1960s programmer, I didn’t use any extra memory for this generalization, and instead reused a bunch of fields that Knuth was already allocating in MCC. It makes the code really hard to understand and I wouldn’t normally do this but it means that bigger problems can fit in cache, and that means SPEED.

Credit and references

Most of this work is based on Knuth’s TAOCP 4B, which has a whole chapter on Dancing Links and Exact Cover problems.

I forked Aaron Windsor’s implementation of MCC to write mccw.

I used Brian Berns’ solver to check that my code was producing the right solution counts.

My code is on GitHub:

• pips solver
• mccw