Puzzles proven solvable: pairing every level generator with a solver

A generated level that can't be finished is the worst bug a puzzle game can have, and nobody who builds the game ever sees it. It exists for one seed. The person who draws that seed finds it after five minutes of trying, assumes they are the problem, and closes the game.

We wanted generated levels anyway, so the games wouldn't go stale. The architecture contract has one sentence about it: every generator returns a level that is solvable or playable, and ships a test that runs thousands of seeds. If you only came for the counts, here they are. The rest of this is how each game earns its row.

Table for Six#

In the prototype there was one table with six seats, which makes 720 seatings, so it simply tried them all and kept a set of wishes that allowed three answers or fewer. The real game seats up to ten, and 10! is 3.6 million. Its solver cuts each guest's possible seats with their "where" wishes (by the window, at an end, at the kids' table) before anything else, seats the most constrained guest first, and after each placement re-checks only the wishes that guest is part of. Because a clever solver can be cleverly wrong, it is checked against brute force too, on 150 random sets of wishes for each of eleven layouts of up to seven seats, where brute force is still quick, and the two have to agree on every solution. The bigger tables lean on the checks below.

Getting exactly one answer turned out to be the easy part. What we cared about was whether you could get there by thinking. A table is good when it unfolds like a chain: Grandma must sit by the window, so Maya sits across from her, so Leo can only go here. A second module plays the table that way, in passes. Each pass reads every card against what the last one settled and narrows where each guest could sit. The count of passes that changed anything is the table's depth. If the passes alone seat everybody, the table can be solved without a single guess. A hard table has to be solvable that way, with one answer, and reach a depth of 2, 3 or 4 passes depending on how many people are eating.

There are 29 layouts across the five households, and the test lays 60 tables for every one of them at each of three difficulties. For each one it checks that the starting seating is wrong, that at least a third of the guests start out unhappy, that every wish can be broken by some seating (otherwise it's decoration), and that par really is the shortest number of swaps, which is checked against a breadth-first search. On a quarter of them it also strikes out each wish in turn and requires the table to open up to more answers, so no card is along for the ride. Today's table gets checked for every day of a year.

Loose Ends#

The prototype already built each board backwards, from a drawing with no crossings, and scrambled it. That stayed. The new mechanics are all ones the drawing already obeys: pins nailed where the drawing has them, knots with a zone drawn around their home, pairs of pins that move together, colored threads that may cross only their own color, and elastic threads with a length limit.

An answer existing doesn't mean you can reach it, since an elastic limit can block the way. So a reference solver plays each board from the scramble, one legal drag at a time, always picking the drag that clears the most crossings, and stops at the first clean board. The test replays that path through the real engine, and it has to solve the board and earn three stars. It runs 300 seeds for each of eight mixes of mechanics, on boards of 5 to 40 pins.

The number of drags the solver took becomes par. We would have liked par to be the true minimum, but the fewest-moves untangle is NP-hard, meaning there is no known fast way to work it out, so par is a greedy bar that knows where every pin belongs. You can beat it, because nothing makes you put a pin where the solution has it.

The Week#

Ordinary weeks are proven by a greedy player on the real engine, with the same deals and the same mercy piece a person gets: 6 packs, 12 difficulties, 40 seeds each, 2,880 weeks in all.

Puzzle weeks needed something stronger. The page is mostly booked, and you get a fixed hand of pieces that fills the open hours exactly. The generator makes one by tiling a blob of open hours with the pack's own shapes, so it holds an answer from the start. The test throws that answer away and hands the page and the hand to an exact-cover search, a solver that tries to fill every open hour with no overlap, which has never seen the tiling. It has to find its own way through all 2,160.

Paper Plane#

The notebook never ends, so here the proof is a pilot. The bot flies the way a decent player does with one thumb: look a little ahead, climb only with speed to spare, let go before the wing stalls. We kept it from searching the future, because a line only a perfect planner could fly is no use to someone on a bus.

It flies 2,400 pages across five notebooks, and with the best of the three folds it has to fly 99.5% of them cleanly. With the Dart alone it has to fly 99% of a separate 500-page sample. Hands off the controls, a Dart flight has to come down within about four pages, and a skilled one has to go at least twice that far.