Charlie KrugThe Build Log

← All posts

Every puzzle in this game is provably solvable. Here's the trick.

Shove generates endless Sokoban puzzles by playing a solved board backwards, so every level it hands you is guaranteed to have a way out.

Random puzzle generators have a dirty secret: most of them can't promise the puzzle has an answer. They scatter walls and boxes, cross their fingers, and let you find out the hard way, ten minutes into a board that was broken from the start.

Shove is my fix for that. It's a browser Sokoban game (push the crates onto the pads, don't wedge them into corners) that invents a brand-new level every time you ask. The catch that isn't a catch: every single level is solvable, and not because a tester checked it. It's solvable by construction.

Play the game backwards

The generator never builds a puzzle and then asks "can this be solved?" It starts from the answer. First it places boxes already sitting on their targets: a finished, trivially solved board. Then it plays Sokoban in reverse. Instead of pushing boxes, it pulls them, one legal reverse-move at a time, walking the board backwards into a scrambled state.

Here's why that works: every reverse-move is, by definition, a forward-move undone. If the generator pulled a box seventeen times to get from the solved board to the puzzle it hands you, then at minimum, those seventeen moves in reverse order are a valid solution. The guarantee costs nothing. No solver pass, no rejection sampling, no luck.

Difficulty is just how hard the generator scrambles: Easy is a 7x7 board with one box a few pulls from home, Hard is a 9x9 tangle with three boxes and a deep scramble. They feel genuinely different because they are structurally different, not the same board with a timer.

The solver will show its work

Since a solution always exists, Shove can afford a Solve button. On small boards it runs plain breadth-first search; on bigger ones it switches to A* with a box-to-target distance heuristic. The status line tells you which algorithm ran and how many moves it found, then animates the path so you can watch the escape you couldn't see. Getting un-stuck is a feature, not a shame.

My favorite detail from the build has nothing to do with search: the game ships zero audio files. Every sound (the shove, the click of a crate landing home, the two-note win chime) is synthesized live in the browser with the Web Audio API. The whole game is plain HTML, CSS, and canvas. No backend, no login, and the Copy Link button encodes the seed in the URL, so you can send a friend the exact board that stumped you.

Try it

Open it, hit New level, and push crates with arrow keys, WASD, or a swipe. When you wedge a box into a corner (you will), press Z to undo, or hit Solve and watch the search dig you out. Then bump the difficulty to Hard and see how long "guaranteed solvable" keeps feeling like a comfort.

Shove is live. Free, in your browser, no signup.

This post is part of the build log: every app my automated factory ships gets written up here, honestly. Browse everything at apps.charliekrug.com, or subscribe via RSS. Comments are open below.

Comments

Loading comments…