My two year old taught me constraint solving

Reading on email? The visualisations will work better in browser.

My son is two years old, which means he has an Apollonian will to power and loves all kinds of mechanised transportation and earthworks machinery. His particular joy is “playing choo-choo” with a Brio wooden train set. Since he likes me to be involved, but I am expressly NOT permitted to touch the trains, I amuse myself by building interesting track layouts.

After a long while, I began to think more systematically about Brio. The pieces are clearly designed to fit together into shapes, so what’s the underlying structure in the design? Given out set of pieces, what is the most elaborate layout I can build?

I don’t have a formal maths background, but I could see that this was an interesting algorithms problem lying on the floor in front of me. As I explored this, my son demonstrated a hitherto undetected expertise in constraint solving. The rest of this post is a lightly editorialised account of what he told me.

Brio is a wooden train toy for kids but has been documented in depth by particularly interested adults. I first turned to the unofficial Brio track guide , which gives every piece a letter code and a measurement. A is the 144 mm medium straight. A1 and A2 are 108 mm and 54 mm variants. E is the standard curve, an eighth of a circle, measuring just over 182 mm on the inner edge and 222 mm on the outer. Eight of those 45-degree curves therefore enclose a circle about 40 cm across. Most pieces can be flipped over, so a curve can bend left or right depending on how you arrange it.

You get ramps and bridges too, but let’s ignore them and treat the system as two dimensional for simplicity. This suits me because the bridges are quite rickety and my son keeps knocking them over, so I try to hide those pieces.

One morning I begin by putting eight curves together to form a circle.

Good! Reading Shapes with Thomas the Tank Engine and his Friends for hundreds of times has paid off.

But this is the simplest possible closed Brio loop. Where do we go from here? What sounds fun to me is to take a set of track pieces and find whether every one of them can be arranged in a closed layout (i.e. with every connector paired up).

This post features visualisations powered by three solvers of increasing sophistication. Figures one to four run a backtracking search, figure five uses constraint solving, and figure six uses a SAT solver.

The backtracking search builds the track the way a toddler would: put down a piece, look at the open connectors, try another piece, back up when something doesn’t fit. Here’s how we’d make a loop:

Pieces on the floor Search trace 0 pieces placed 0.0s elapsed 0 states explored 0 open connectors Current choice No track placed yet. This visualization needs JavaScript. The solver's result for the default set of pieces is an eight-piece closed circle of 45-degree curves. Actually, my son throws the choo-choo in a rage when the track doesn’t fit, but the solver performs recursive backtracking instead, a common way to explore a search space for those with self-control.

The open connectors form a task list. The solver works on just one of them at a time, trying every piece and orientation that fits there and recursing into each. When a branch hits a dead end — no piece that can fit, or every piece used up while connectors are still open — it backs up to the last connector that still had options. The track only counts as closed once no connectors remain open and every piece in the set has been placed. Closing early with pieces still spare is treated as another dead end to back out of. In Python-style pseudocode, it would look something like:

def search (open_connectors, unused_pieces, layout): if not open_connectors: return layout if not unused_pieces else None connector = open_connectors[ 0 ] for piece in unused_pieces: for port in piece . ports: placement = mate(piece, port, connector) if collides(placement): continue found = search(update(open_connectors, placement), unused_pieces - piece, layout + placement) if found is not None : return found return None With eight E curves, the problem is pretty trivial as long as you lay every curve facing the same direction. The solver doesn’t know that, though. If you step through the figure above and watch the “states explored” count, it will jump up very quickly. That’s because the search first tries a curve bending the wrong way, following that dead end until it runs out of pieces without ever closing, then backing out and laying the curve that actually works. The “states” count tracks that whole wasted subtree.

So I make the track bigger by splitting the circle and adding some parallel straight sections on opposite sides.

“Oval!” I say, as if I’ve discovered geometry.

“No, Dada, oblong ,” he says, pointing at the straight sections.

I stare. He’s right. His nursery worker had said he seemed quick. Perhaps the fees were worth it after all.

Trying to quickly recover authority, I consider the algorithmic impacts. Adding two straight pieces dramatically increases the number of possible states.

Pieces on the floor Search trace 0 pieces placed 0.0s elapsed 0 states explored 0 open connectors Current choice No track placed yet. This visualization needs JavaScript. The solver's result for the default set of pieces is an eight-piece closed circle of 45-degree curves. The obvious approach uses a greedy algorithm: take the first piece that fits, keep going, and never look back. But a piece can fit in one place and still make it impossible to ever close the track. The straight pieces in particular only work in a few positions. A greedy run would use one of them in the wrong place, get stuck, and have nothing left to do about it. So we want the ability to backtrack from dead ends, unwinding the placements we’ve made and trying a new piece.

I explain this gently. “Exponential, Dada,” he nods.

Indeed. Every open connector can be continued by any piece that fits it, so the number of partial layouts grows exponentially with the number of pieces, very roughly O(b^n) for a branching factor b and n pieces. This figure has only two more pieces than the previous circle, but it tries 1,930 states against the circle’s 254. That’s about eight times as many states for two extra pieces.

So if it’s an algorithm with exponential running time, how is it running reasonably quickly in your browser? At this size, it doesn’t need to be clever: a couple of thousand states is nothing for a laptop to chew through, so plain exhaustive backtracking — trying every piece and port in a fixed order, no shortcuts, no cleverness — finishes in milliseconds. That won’t stay true forever. The worst case is still exponential, and we’ll hit the wall soon.

Anyway, circles and oblongs or ellipses or ovals or whatever you call them are boring. It’s not hard to make a bigger one but the trains just go round the same. We need crossings and branches to make things interesting.

My son picks up a crossing piece (H3). It’s made from two overlapping circles so a train rolling through can stay on its groove or switch to the other line.

Now we have branching points! I show my son. “Look, we’ve got a crossing piece here.”

I melt with pride. My own little computer scientist! A future terror of Hacker News comment sections!

As we saw in the graphs section of The Computer Science Book , a graph is the mathematical term for points joined by lines (the points are vertices, the lines are edges), and a cycle is any route through the graph that comes back to where it started. Every track piece up to now had two connectors, so the track was like a single thread, going from one end and round to the other. One cycle, if it formed a closed loop. The crossing has four connectors, so placing it opens three connectors at once and the search itself starts to branch. The data model had to change from this:

piece = connectors + geometry + internal grooves The search algorithm didn’t change but it is now searching over a more complex space.

The goal, remember, is to check whether every piece in the set — crossing included — fits into one closed network. And it does. Two full circles joined through the crossing, every connector paired, and the train threading both grooves on a single lap.

Pieces on the floor Search trace 0 pieces placed 0.0s elapsed 0 states explored 0 open connectors Current choice No track placed yet. This visualization needs JavaScript. The solver's result for the default set of pieces is an eight-piece closed circle of 45-degree curves. An interesting sidenote is collision detection. Initially, I added this as a constraint because the solver kept trying to cheat by laying pieces over the top of each other. I added it for correctness but the extra constraint also helped speed up the search. More constraints reduce the size of the search space that has to be explored.

Subscribe and I'll send you a free, 45-page roadmap through computer science — what to learn, in what order, and what to skip — plus the occasional CS deep dive.

The L branch is a straight and a curve sharing one connector. The choo-choo can carry on straight or peel off around the curve. The M is its mirror image.

The solver can now find more interesting layouts. It creates an inner loop between the two branches so that there’s an oblong on the outside, a circle on the inside, and every one of the branches’ three connectors is paired.

Pieces on the floor Search trace 0 pieces placed 0.0s elapsed 0 states explored 0 open connectors Current choice No track placed yet. This visualization needs JavaScript. The solver's result for the default set of pieces is an eight-piece closed circle of 45-degree curves. “Dada! Degree three. No Euler circuit.”

After consulting with ChatGPT, I understand what my son means.

Degree just counts how many track-ends meet at a point, so the crossing (four connectors) is degree four and the branch (three connectors) is degree three. As my son explained, graph theorists call the track shape a theta graph, because it looks like the letter θ. Euler proved in 1736 that a vertex of odd degree means that single lap cannot cover every piece of track exactly once. (Euler had bridges in mind, not wooden trains, but the beauty of maths is that the insight transfers). The crossing has an even degree and that means a choo-choo can follow the full figure-of-eight in a single lap. When we use branches, the track is fully closed but the train can’t cover the full path in one lap.

My track layouts have stopped impressing my son. Desperate, I try to make the most impressive track yet: lots of crossings, lots of branches, the whole works.

I tip the whole set of pieces out onto the floor and try to make a super duper complex layout. I fail pretty badly. I get so far and then find that pieces are just too far apart to connect. The search space is exponential in the number of pieces, and here I am adding pieces.

My son watches me with an implacable stare before finally sighing with the heaviness unique to two-year-olds.

“Dada,” he says, “this is a constraint satisfaction problem, silly billy!”

“What do you mean?” I ask, not without some frustration because I dimly suspect he has a point.

“Variables are the open connectors. Domain is the pieces that still fit. Constraints say every connector pairs!”

Of course! How had I missed this? In normal language, a constraint satisfaction problem is what you get when you can say three things:

Sudoku, for example, is basically a constraint satisfaction game. No row, column, or box can repeat a digit, so you have to work out where they can fit. This is what constraint solvers do.

Translated to Brio, the choices are where the pieces go. The allowed values are the positions, rotations, and flips they can take. The constraints are the physical rules we’ve been gathering: connectors have to meet, track can’t pass through track, etc.

If you stop to think about how backtracki