Light the whole sky with the fewest matches. A daily cascade puzzle whose minimum score isn't tuned by a designer — it's proved by a theorem.
▶ Play it: https://minhnguyen1406.github.io/matchless/ (new board every day; works offline; installable as an app on iPhone/Android via "Add to Home Screen")
Firework shells sit on a grid. Each shell has fuses (arrows) pointing at neighbours. Strike a match on a shell and it bursts — and its fuses ignite every shell they point to, which ignite their neighbours, chain after chain. Clear the sky in the fewest matches.
- Daily — one board a day, the same for everyone, with streaks and a spoiler-free share card.
- Practice — twelve curated boards from easy to expert.
- Duel — alternate matches with a friend or the search bot; fewest shells wins.
- X-ray — see the components the proof counts.
- Editor — build a board, watch par recompute, and send it as a link.
"Given a directed network, what is the smallest set of starting points whose cascade reaches everything?" is not only a puzzle question:
- Build systems and cache invalidation — which minimal set of modules must you rebuild so every downstream artifact is refreshed?
- Grid black start — after a total blackout, which generators must be started by hand so the rest of the grid can be energised from them?
- Garbage collection — a GC root set is exactly a set of seeds whose reachability decides what survives.
- Influence maximisation — the probabilistic version of this question is NP-hard; strip the probability out and it collapses to the clean answer below. Knowing which side of that line you're on is the whole trick.
Model the board as a directed graph: shells are vertices, fuses are edges.
- Contract every strongly connected component (Tarjan's SCC, one DFS pass) into a single super-node. The result is the condensation, which is a DAG.
- In a DAG, a component with an incoming edge never needs a match — something upstream will always reach it. A component with no incoming edge can only be lit by a match.
- Therefore par = the number of source components, exactly. One match inside each source is sufficient; one per source is necessary.
That's the proof, and the X-ray button draws it: every component in its own colour,
every source ringed. Verify.java then refuses to take my word for it — across 2,898
checks it brute-forces every subset of taps and confirms no smaller set ever
clears the board.
The difficulty model. I assumed difficulty came from look-ahead: greedy players grabbing big cascades would miss the optimum. Measured over 5,000 boards, greedy matched par 100% of the time — my model was wrong, and the 100% was a second theorem (any node upstream of your choice has a strictly larger reach, so greedy never picks a non-source while a source would do better). So difficulty was redefined around what players actually get wrong:
| rate on random 6×6 boards | |
|---|---|
| Myopic play (biggest immediate fan-out) costs at least one extra match | 87.1% |
| …at least two | 56.0% |
| At least one source hidden inside a cycle, where "tap what nothing points at" fails | 86.0% |
| …at least two | 54.7% |
The duel's rule. The obvious two-player rule — most shells wins — turned out to be solved by greed: grabbing the biggest cascade is optimal on all but a fraction of a percent of boards. Inverting it fixes the game, so the shipped rule is fewest shells wins, where the danger is being forced to set off a huge cascade:
| duel rule | boards where the obvious move is not optimal |
|---|---|
| most shells wins | 0.0% (4×4), 0.6% (5×5) |
| fewest shells wins (shipped) | 29.1% (4×4), 35.5% (5×5) |
Verify pins a counterexample board for each rule, so both claims are executable
rather than remembered.
The daily board is defined as the first board a seeded generator produces that clears the daily bar — no server generates it and nothing is stored, so the browser rebuilds it offline. That's only honest if the JavaScript agrees with the Java exactly, so:
- randomness is SplitMix64 over 64-bit integers (verified against the algorithm's published reference vectors), never floating point;
- Java finds components with Tarjan, JavaScript with Kosaraju — two different algorithms agreeing is a stronger check than one transcribed twice;
tools/crosscheck-daily.jsruns both over 120 days of boards and compares fingerprints, plus round-trips every board code across the language boundary. It runs in CI on every push.
| Where | What |
|---|---|
Solver.java |
Tarjan's SCC (recursive DFS, low-links), condensation DAG, par proof |
Duel.java |
minimax over unlit-shell sets, memoised; two rules behind one comparator |
NodeSet.java |
hand-rolled bitset over long[], verified against java.util.BitSet |
Board.java |
grid → directed graph; BFS reachability |
Codec.java |
bit-packed board serialisation with a checksum, mirrored in JS |
Rng.java |
SplitMix64; Lemire bounded ints; Fisher-Yates written out for portability |
Verify.java |
exhaustive brute force and naive reference implementations as oracles |
Stats.java / Generator.java |
Monte-Carlo measurement driving both design decisions |
docs/game.js |
undo/redo over two stacks; BFS depths drive the cascade animation |
| OOP | Direction enum with geometry, Node/Board encapsulation, solver separate from generation, rules as an enum, zero global state |
engine/src/main/java/matchless/ the engine: graph, solver, duel, codec, rng, verification
docs/ the playable site (GitHub Pages serves from here)
engine.js the same engine in the browser
game.js index.html the game
editor.js editor.html the board editor
tools/ cross-language check and icon generation
javac -d out $(find engine -name '*.java')
java -cp out matchless.Verify # 2898 checks, 0 failures
java -cp out matchless.Stats 5000 # the measurements quoted above
java -cp out matchless.Daily # today's board as JSON
java -cp out matchless.PuzzleGen 3 > docs/puzzles.json
node tools/crosscheck-daily.js 120 # java and javascript agree, board for boardThen open docs/index.html, or python3 -m http.server -d docs.
Cascade-on-a-graph has good company — Arrowed (mobile), Infini-Node, toppling-dominoes positions in combinatorial game theory, Pushover (1992) — but I couldn't find a game built on provable par via SCC condensation, with difficulty measured as myopic-gap/hidden-sources. "Matchless" was chosen after searching app stores and Steam for collisions (earlier candidates Topple, Chainfall, and Fuseworks all collided with existing games or studios).
MIT — see LICENSE.