두 살 아들에게 배운 제약 충족 문제(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. The Brio system 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. First, make the track close One morning I begin by putting eight curves together to form a circle. “Circle!” my son cheers. 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: 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. “More, Dada!” he says. Making the track bigger 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. 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. Crossings add branching points 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.” “Graph with two cycles!” he beams. 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 = geometric move to 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 t