A Diffusion Model Learns PSPACE-Complete Solvability From Tile Completion Alone
A masked diffusion model trained only to fill in Sokoban tiles achieves 77.4% puzzle solvability with no solver, reward, or constraint label in the loop.
Deciding whether a Sokoban puzzle is solvable is PSPACE-complete. That means solutions can be exponentially long, there is no short certificate to verify one exists, and even a single misplaced wall can silently break the whole board. The conventional assumption follows: generating solvable puzzles requires either a solver in the loop, explicit solvability labels, or some form of constraint supervision. None of those are true.
A transformer-based masked diffusion model, trained purely on tile completion with no solver access, no reward signal, and no solvability labels, produces puzzles that are solvable 77.4% of the time. Of the remaining failures, 94.5% become solvable by removing a single wall. The model was never told what solvability means. It learned the global property from a local objective.
The mechanism is structural, not accidental. An autoregressive model factorizes generation as a strict left-to-right prefix: each cell is conditioned only on what came before it in a fixed order. Masked diffusion breaks that constraint. It hides a random subset of cells and learns to predict any one of them given any other subset already revealed, so at generation time cells can be filled in any order, each one conditioned on the full partial board regardless of position. Sokoban solvability is exactly a non-local property: a box placement in one corner constrains what is possible three moves away in a different part of the grid. A generator locked into a fixed left-to-right order is a structural mismatch for that kind of problem. Masked diffusion is not.
The training pipeline adapts MD4 (Shi et al., 2024) and trains on DeepMind's Boxoban dataset. No search, no planner, no constraint oracle. 77.4% solvability, with near-total recoverability of failures at the cost of one wall removal. For teams building constrained generative systems, the takeaway is direct: constraint satisfaction may not require explicit constraint supervision when the generation architecture is a structural match for the constraint's dependency structure.
We're thinking: We find the most pointed implication here is not about Sokoban. It is about what "emergent" actually means in the context of constraint satisfaction. The standard assumption in constrained generation is that you need to either supervise the constraint directly or inject it through a reward signal. This result suggests a third path: choose an architecture whose inductive bias matches the dependency structure of the constraint, train on a simpler local objective, and the global property may follow. That is not a guarantee, and it is worth noting the 77.4% ceiling still leaves a meaningful failure rate for production use. But the direction is worth watching, especially for teams generating structured artifacts like code, layouts, or circuit designs where global validity is hard to supervise and local completion signal is cheap.
Key takeaways:
- Masked diffusion's order-agnostic conditioning, predicting any cell from any subset of revealed cells, is a structural match for non-local constraint problems that fixed-order autoregressive generation is not.
- The model achieves 77.4% puzzle solvability with 94.5% of failures recoverable by a single wall removal, trained entirely on tile completion with no solver, reward, or solvability label; the 22.6% failure rate means it is not a drop-in production generator without a lightweight post-filter.
- Teams generating structured artifacts with hard global validity constraints should audit whether their generation architecture's conditioning order matches the dependency structure of the constraint before adding solver-in-the-loop machinery.