Move / push: arrows or WASD Undo: Z — the whole game, one move at a time Redo: X Restart level: R Show trap squares: T Solve it: V Change level: Q back, E forward Next level after solving: SPACE OPTIMAL in the HUD is the true minimum push count for that level, measured offline by the solver in tools/mklevels.py — so it is a target, not a guess.
Twelve hand-drawn levels, full undo/redo, a deadlock detector that reasons about the level rather than the move, and a push-optimal breadth-first solver that will play any of them for you. THE INTERESTING BIT Undo is not a snapshot. Sokoban has no inverse move: you push, you never pull. So each move is stored as a single number — the direction, plus one bit for whether it pushed — and undoing it steps the player back and, if it pushed, pulls the box onto the cell the player just vacated. One list item per move instead of a whole board copy per move, and O(1) either way. Redo is the same array with a cursor; making a fresh move truncates the tail, which is exactly what a text editor does. Deadlock detection needs two different ideas. The dynamic one is a *frozen 2x2*: any two-by-two block of walls-and-boxes holding a box that is not on a goal, because none of those four things can ever move again. The static one is better: press T. Those trap squares are computed once per level by running the game backwards — put a box on every goal and repeatedly pull it, which needs the destination and the square beyond it to both be floor, the exact mirror of a push. Every floor square the pulls never reach is a square from which no box can ever reach any goal. That finds the four obvious corners, but it also finds entire runs of wall with no goal on them, which is the case a corner check misses and the case that actually kills runs. The solver searches pushes, not steps. A node is (which cells hold boxes, where the player ended up); an edge is one push; so the first goal state BFS reaches is reachable in the fewest possible pushes. Two details make it work at all inside Scratch: - Visited states live in a real 8192-bucket chained hash table built out of two lists (bucket heads plus a next-pointer per node). Scratch's list contains is a linear scan, so using it would make the search quadratic in the state count — 20,000 states would mean 200 million comparisons. - The state keeps the player's exact cell rather than a normalised representative of its reachable region. The textbook choice is to normalise, and tools/mklevels.py --cost confirms it gives 3–7× fewer states. But normalising needs a flood fill of the room per successor rather than one per expanded node, which is roughly 8× more work per node — so measured end to end, the naive representation wins. Numbers for the shipped levels: | slot | pushes | states, normalised | states, exact player | |---|---|---|---| | 3 | 6 | 60 | 187 | | 7 | 12 | 1,870 | 8,010 | | 10 | 14 | 1,134 | 5,654 | | 11 | 26 | 2,051 | 9,442 | | 12 | 46 | 14,224 | 93,183 | The search runs 100 nodes per frame from a yielding loop, so the node counter climbs on screen instead of the project appearing to hang. When it finds a solution it converts the push list into a full walk-and-push step sequence — each walk is its own shortest-path BFS — and replays it through the ordinary move code, so the undo history fills exactly as if you had played it and you can Z back through the machine's solution. All three were checked against the compiled .sb3 in the headless scratch-vm harness, not by reading the code: - Solver. Level 3 (OPTIMAL 6): V expanded 136 states, found a 6-push solution, expanded it into 14 steps and replayed them to SOLVED. Six is the proven minimum, so it found an optimal solution, not merely a solution. - Deadlock. All original - code, art and sound. See Inside is open.
