History of the genre

The origins of Sokoban

Sokoban-Lettres did not invent its mechanic: it borrows it from a Japanese game from 1982 whose formula has barely changed since. Understanding where that formula came from helps explain why it has aged so well — and what adding letters changes about it.

A warehouse keeper

The word sōkoban (倉庫番) means “warehouse keeper” in Japanese. The game is the work of Hiroyuki Imabayashi and was published in 1982 by Thinking Rabbit, a Japanese studio for which it became the first notable title. It appeared on the Japanese home computers of the day, at a point when the computer puzzle game was still a genre in the making.

The principle fits in one sentence: a character pushes crates around a warehouse seen from above until every crate rests on a marked spot. He cannot pull them, cannot push two at once, and cannot walk through walls.

Why so few rules are enough

Most games gain depth by adding systems. Sokoban does the opposite: its depth comes from a single asymmetry. Pushing is possible, pulling is not.

That asymmetry has a brutal consequence — most moves are irreversible. In a sliding-tile puzzle, any position you reach can be undone. In Sokoban, a crate pushed into a corner stays there forever. The player does not lose through lack of dexterity; they lose through poor anticipation, sometimes thirty moves earlier, with nothing signalling it at the time.

This also explains the genre's distinctive feel: the decisive moment of a game is almost never the moment you notice the failure.

A hard problem, in the technical sense

Sokoban attracted the attention of artificial intelligence researchers early on, and not out of curiosity: it is a particularly hostile test bed for planning algorithms.

Work carried out in the 1990s established that the generalised version of the game — on an arbitrarily large grid — is PSPACE-complete. In plain terms, it belongs to a difficulty class for which no efficient general solution method is known, and it is at least as hard as anything else in that class. Earlier results had already shown it to be NP-hard by relating it to motion planning problems.

What makes Sokoban hard for a machine is not the number of moves available at any instant — that number is low, often under ten — but the depth of the solutions and the presence of unrecoverable positions. A naive search spends hours exploring branches that were doomed long ago. Effective solvers therefore devote most of their intelligence to a single task: recognising as early as possible that a position is lost.

Forty years of ports

Sokoban spread as few games have: its logic fits in a few dozen lines of code and its levels in a few bytes of text. It has been ported to practically every platform since, often by hobbyists, often alongside level collections built by enthusiasts. Reference level sets are still used today to benchmark solvers against one another.

That spread owes a great deal to a rare property: a Sokoban level is data, not a program. A grid can be written out in characters — wall, floor, crate, target — which allowed thousands of levels to circulate independently of any particular implementation.

What the letters change

In traditional Sokoban the crates are interchangeable. The problem is to cover a set of spots; which crate occupies which does not matter.

Sokoban-Lettres removes that freedom. Each crate carries a letter, the spots spell a word read left to right, and a crate marked “R” now has exactly one possible destination. The problem stops being a set-covering task and becomes a constrained assignment: you must not only get every crate home, but do it in an order where none of them blocks another one's route.

The effect is striking on modestly sized grids. A layout that would be trivial with anonymous crates can demand real thought once the order is imposed, because every letter already placed becomes an obstacle for the ones still to come. That is what makes it possible to keep grids readable on a phone screen without giving up difficulty.

A second, less expected effect concerns memory. The target word gives the player a handle that classic Sokoban does not offer: “the R has to go before the O” is easier to hold on to than an abstract position. The difficulty modes play on exactly that, by hiding some or all of the labels.

Read on

The full rules of this variant are set out in the guide, and the design decisions on the about page. The Daily Challenge offers one grid per date, identical for everyone.