Solvable Sokoban Without a Solver via Diffusion
| Source: arXiv AI
Tags: diffusion models, constrained generation, masked diffusion, puzzle generation, game AI, discrete diffusion
A masked diffusion model trained only on tile completion achieves 77.4% solvable Sokoban puzzle generation with no solver access, rewards, or solvability labels — demonstrating that global PSPACE-complete constraints can emerge from local masked training objectives.
Details
Deciding whether a Sokoban puzzle is solvable is PSPACE-complete (Culberson, 1997) — solutions can be exponentially long and there is no short certificate. This paper shows that a transformer-based masked diffusion model trained purely on tile completion achieves 77.4% solvability, with 94.5% of the remaining failures fixable by removing a single wall. The model was given no solver access, no rewards, and no solvability labels. The architecture insight: masked diffusion hides a random subset of cells and learns p(cell | any subset), rather than always conditioning on a prefix like autoregressive models. At generation time it can reveal cells in any order, each conditioned on everything already placed. This better matches the non-local constraint structure of Sokoban — a decision in one board region can constrain what works elsewhere. Adapted from MD4 (Shi et al., 2024) and trained on DeepMind's Boxoban dataset, the model and generation code are publicly released. The broader claim — that global, search-heavy properties can emerge from local masked training without explicit supervision — has implications for any constrained generation problem where autoregressive models struggle.