Chain reactions as graphs: the maths behind a Carillon tap

Carillon looks like a toy: tap a dot, watch the rings. Underneath is a small piece of graph theory, and it is what lets the game promise that every level is fair and every hint is right. Here it is with as little notation as possible.

A field is a graph

Treat every dot as a point, and draw an arrow from dot A to dot B whenever A’s ring reaches B. In the game’s terms, that is when the distance between their centres, minus B’s radius, is no more than A’s reach.

That picture is a directed graph: points joined by one-way arrows. A big dot can have an arrow to a small dot with no arrow back, because the small dot’s reach is short.

When you hold a dot in the game, the outline shows exactly its arrows: every dot its own ring touches.

A chain is a shortest-path search

A ring grows at 480 units a second, and a live dot pops the moment the front reaches its edge. So each pop time is the earlier pop time plus the travel time along the arrow.

The game runs this with an event queue: take the earliest pending pop, skip it if that dot has gone, otherwise pop it and queue every live dot its ring reaches. That is Dijkstra’s shortest-path algorithm, the one behind route finding. Since every travel time is positive, a dot’s first exit from the queue is its true earliest pop.

Here is a small example the game’s tests use. A big dot has two normal dots in a line, 130 and 250 units away:

• The near dot pops at 0.217 s: the ring travels 104 units to its edge.
• The far dot is inside the big dot’s reach, and that ring would get there at 0.467 s.
• But the near dot’s ring gets there first, at 0.413 s, so that is when it pops.

A dot reached by two rings pops once, from whichever arrives first, and ties go in a fixed order, so a chain always plays and sounds the same.

What a tap pops has nothing to do with time

The timing is for your eyes and ears. For the puzzle, what matters is that a popped dot always sends out its full ring, so a tap pops exactly the dots reachable from it by following arrows: the dot’s closure.

Later taps are easy too. After some taps, anything a popped dot reaches has also popped, so a tap’s chain on what is left is its chain on the full field, minus what has gone. The solver stores each dot’s full chain once as a 64-bit mask, and every later chain is one bitwise AND.

Why the fewest taps is the number of sources

Group the dots into strongly connected components: sets where every dot can reach every other through chains. A pair of dots that reach each other is one; a lone dot is one on its own. Now call a component a source if no dot outside it has an arrow in.

Two facts follow:

1. Every source needs a tap of its own. Nothing outside a source can ever pop it, and popping other dots only removes arrows, so it stays a source.
2. One tap in each source is enough. Follow any dot’s arrows backwards and you must end in a source. So every dot is downstream of some source, and tapping each source once pops the whole field.

So the fewest taps is exactly the number of sources, and the winning first taps are the dots inside them. On screen, a chain start is a dot no other circle touches, or a small group that only reach each other.

Trust, but check

The solver does not rely on this theorem. Its search is plain: try each live dot, skip taps that pop the same set as one already tried, recurse on what is left, and remember every position solved. The theorem sits beside it, and the tests hold the two against each other on 150 random fields and every shipped level. Weakening the theorem’s code by one condition makes both checks fail, so the checks are real.

Difficulty as a formula

The same graph gives the game its difficulty measure. For a one-tap level it comes out as

D = log2( (n + E) / (W + Ew) )

where n is the number of dots, E the number of arrows, W the winning dots and Ew the arrows out of them. More dots and arrows push it up; more winning dots push it down. On a level with more taps, each source is one more find, so every extra tap adds bits of its own. How the levels are made explains where it comes from and how it orders the levels.

What this means when you play

You do not need any of this to enjoy Carillon, but it explains the beginner tips: look for the dot nothing reaches, and don’t trust the one that lights up the most. It is also why the hint is right even after a mistake: a wasted tap never removes a source.