Every box can open: how Hako makes its puzzle boxes

Hako makes three promises, and this post is about how it keeps them.

1. No box can ever get stuck. Whatever you do, it can still be opened.
2. The goal for three stars is the true fewest moves. Nobody can beat it.
3. A box is never easier than the one before it, even at the start of a chapter.

There is a bit of maths in here, but nothing scary. And no answers to any box, promise.

A box is just a few numbers

The first idea makes everything else easy.

A panel in Hako can only slide along its own groove. It can’t turn, it can’t jump, it can’t leave the groove. So everything about one panel is a single number: how far along its groove it sits.

And a whole box is just those numbers in a row, one per panel. If a box has ten panels, any arrangement of it is ten small numbers. Even the biggest box fits in one number on a computer, which makes the box very fast to work with.

A move changes one of those numbers. In Hako, one move is one slide of one panel, any distance, in one direction, because that is exactly one drag of your finger. Sliding a panel all the way across costs the same as one step.

Why a push is refused

When you push a panel, the game asks one question before every step it takes: can this panel go one more stop this way? There are only three reasons it can’t:

1. A pin. The panel is pinned, and the panel with its mark is not on its ring.
2. The groove ends. The next stop is outside the groove.
3. Another panel. Something is in the way.

When a push is refused, the reason lights up. The panel in the way flashes, or the end of the groove glows, or the pin and its key’s mark blink with a dashed line to the ring.

The nice part is that the program that solves boxes uses the very same question. So what the game tells you and what the game knows can never be different.

Why the pins are in the panels

The first version of Hako had pins in the floor, not in the panels. A pin stuck up out of a floor cell and blocked it, dropped down while its key sat on a ring, and sprang back up as soon as the cell was uncovered.

It looked cool, and it was a disaster.

Because of that spring, some moves became one-way. A panel could slide off a pressed pin, the pin would pop up behind it, and the panel could never come back. So a few wrong moves could ruin a box for good, and you would only find out much later. Also, a pin hidden under a panel was a surprise you had no way to read.

So I moved the pins into the panels. Now a pin goes through a panel and holds that panel still, and whether it holds depends only on where its key panel is. That one change means:

• every slide has a slide straight back. Moving a panel never changes whether that same panel is pinned, and never moves any other panel.
• no box can get stuck. From any arrangement you can reach, you can get back to the start, so you can always still open it.
• nothing is hidden. The pin head, the key’s mark and the ring are always drawn.

The program that makes boxes also refuses any loop of keys, like A’s key being B and B’s key being A, which could hold both shut forever.

The goal is the true fewest moves

So how do I know the fewest moves to open a box?

The program does what is called a breadth-first search. It looks at every arrangement one move away from the start. Then every arrangement two moves away. Then three, and so on, never looking at the same arrangement twice. The first time it finds one where the lid can leave, that number of moves is the fewest. Every shorter way was already tried.

The cover of this post is level 1 done that way: every arrangement its panels can take, joined to the ones a single slide away, with the way out in gold. Level 1 is tiny, so its map fits on a page. A big late box has tens of thousands of arrangements.

The goal you see is that number. Meet it and you get three stars. Two stars allow a few extra moves, and the leeway grows with the box:

$\text{leeway} = \max\left(2, \left\lceil 0.4 \times \text{goal} \right\rceil\right)$

So a box with a goal of 13 gives two stars up to 19 moves, and a goal of 40 up to 56. Any opening at all earns one star.

The hint uses the same search, but from where your panels are right now. It lights the first move of a shortest way to open the box from there. So even after a few wrong slides, the hint is still the best next move, not a move from the start.

Making a deep box

Here is the hard part. If you lay out panels at random, almost every box is either trivial or impossible. Deep sliding puzzles are rare.

So the program does not hope for luck. It climbs:

1. Lay out a random box for the chapter: the lid in a middle lane, panels of the allowed sizes, some grooves cut short, and the pins.
2. Map every arrangement it can reach, and measure how far each one is from an open box. It does this from the open end, spreading outwards from every open arrangement at once, which works because every move can be undone.
3. Keep the arrangement that is farthest from open. That is the best start this box can have.
4. Make one small change to the box: move a panel, change its size, shorten a groove, roll the pins again. If the new box’s best start is at least as deep, keep it.
5. Repeat, until the box is as deep as the chapter wants.

Then each box has to pass checks that take something away and solve it again:

• Every pin matters. Take out any one pin and the box must get strictly shorter. A pin that changes nothing is just decoration, and it goes.
• Short grooves matter, in the chapters about them. Make every short groove long again, and the box must get shorter.
• The chapter’s new piece is used. In the chapter of long panels, a long panel must move in the shortest solution. Same for blocks, rails and wide blocks.

The prototype’s generator was written in the game’s own language and took 210 seconds for fifteen boxes. Now the climbing part is in C, and a box of 18 to 24 moves takes about half a second. The game still solves every box again with its own solver, and a box where the two disagree is thrown away.

Why the boxes only get harder

Every box has its fewest moves, and the program picks the boxes in order so that number never drops from one box to the next. Not inside a chapter, and not when a new chapter starts.

You can see the shape in the chart. It climbs fast early, from 2 moves on level 1 into the thirties, and then slowly, about one move a chapter, into the mid forties.

That flat part is a real limit. With this kind of climbing, boxes much deeper than the mid forties are either too big to map or too rare to find. So past that point, the boxes get harder in the other way: more panels with barely a gap, long rails, wide blocks, short grooves that force one order, chains of three and four pins, and lids that are themselves pinned at the end of a chain. The fewest moves is the number that never drops, and the pins are what keep getting harder.

No two boxes alike

Each box is compared with every earlier box of the same size, in every mirror, and on a square box in every turn too. If most of the panels match, the new one is too alike and is skipped. Every box is checked again whenever the game changes: it opens in exactly its goal, every pin is needed, the ramp never drops, and no two are too alike.

The little rewards in between

Knowing every box’s map made two nice extras possible.

Clean moves. When a box opens, the game maps every arrangement once, quietly in the background. Then it knows, after every move you make, whether you got one step closer to open. Moves that stay on a shortest way build a streak, each one a bell a note higher, and at 3, 5, 8 and 12 in a row a word appears: “Neat”, “Clean”, “Masterful”, “Flawless”. There is no clock on the streak, because thinking is the whole game.

Cascades. When one move frees several panels at once, like a key landing on its ring and opening a lane at the same time, the freed panels hop one after another, each with a higher bell. Three or more at once is a “Cascade”.

That is the whole machine. Numbers in a row, one question for every push, a search that always finds the shortest way, and a climb that only goes up. And if you ever think you have found a box that is stuck, try sliding back. It always works.