A neural network taught only to guess missing tiles just picked up a skill nobody trained it for: knowing whether a Sokoban puzzle can be solved at all.
Researchers built a transformer-based discrete diffusion model and trained it purely on tile completion, filling in masked cells of Sokoban boards drawn from DeepMind's Boxoban dataset. The model never saw a solver, a reward signal, or a solvability label during training. When it generated new puzzles, 77.4% turned out to be solvable outright. Of the ones that weren't, removing a single wall fixed 94.5% of them.
Sokoban solvability is PSPACE-complete, meaning there's no shortcut to checking whether a puzzle can be beaten short of exhaustive search, and a single misplaced wall can quietly break the whole thing. That a model trained on nothing but local tile-filling absorbed this global, search-heavy property suggests the diffusion process itself, which can fill in cells in any order rather than left-to-right like autoregressive models, is a better structural fit for problems where one decision constrains something far away on the board.
It's not a solver, and a 77% hit rate still means roughly one in four generated puzzles is broken, but it's a reminder that how a model is allowed to look at a problem can matter as much as what it's trained to predict.