Source-linked AI summary
Solvable Sokoban Without a Solver via Diffusion
Sina Baghal
TL;DR
Sokoban solvability depends on non-local interactions that fixed-order generation poorly matches. This paper trains masked discrete diffusion only on tile completion and finds 77.4% unfiltered solvability, rising to 98.7% after single-wall repairs.
Problem
Sokoban’s spatial interdependencies make solvability a global property that cannot be decomposed into isolated, step-by-step decisions.
Method
A masked discrete diffusion model learns tile completion from randomly masked Sokoban grids without solvers, rewards, or solvability labels.
Results
77.4% of generated puzzles are solvable unfiltered, rising to 98.7% when failures repairable by deleting one interior wall are counted.
Takeaways & Limitations
Solvability can emerge from a local masked-cell objective, suggesting the model inherits this global property from the learned training distribution.
Takeaways & Limitations
The evaluation relies on held-out puzzles drawn from the same distribution as the training data, making distributional scope an explicit boundary.
Abstract
from arXiv · showhide
Deciding whether a Sokoban puzzle is solvable is PSPACE-complete (Culberson, 1997): solutions can be exponentially long and there is no short certificate to check. Solvability is also a fragile property, since even a single misplaced wall can silently render an entire puzzle unsolvable. In this work, we show that a transformer-based discrete diffusion model trained purely on tile completion, with no access to solvers, rewards, or solvability labels, achieves a solvability rate of 77.4%, with 94.5% of the remaining failures rendered solvable by removing a single wall. In other words, a global, search-heavy property follows from a local training objective: trained only to fill in masked cells, the model inherits solvability it was never trained on. An autoregressive model factorizes as $p(c_k \mid c_1 \dots c_{k-1})$, meaning a fixed order, always conditioned on a prefix. Masked diffusion does not: it hides a random subset of cells and learns $p(c_k \mid \text{any subset})$, so at generation time it can reveal cells in any order, each one conditioned on everything already placed, wherever it sits on the board. A puzzle's difficulty comes from exactly this kind of non-local interaction, a decision in one part of the grid constraining what will work somewhere else entirely. A generator that is not locked into a single fixed order is therefore a better structural match for the problem than one that is. The training pipeline is adapted from MD4 (Shi et al., 2024) and the dataset is DeepMind's Boxoban (Guez et al., 2019). The trained model and instructions for generating puzzles are publicly available.
1 Preliminary
The preliminary section introduces Sokoban, explains solver-based solvability and difficulty measurement, and then presents masked diffusion for puzzle generation. It also covers masked diffusion’s mechanism, development from continuous diffusion, and suitability for Sokoban.
- Sokoban fundamentals: The section first defines Sokoban, push-based solvability assessment, and puzzle-difficulty measurement.
- Masked diffusion: It then describes masked diffusion’s mechanism and evolution from the continuous-diffusion formulation.
- Masked diffusion: The section explains why masked diffusion is suitable for generating Sokoban puzzles.
1.1 Sokoban
Sokoban is a push-only grid puzzle in which moving one box can change reachability, obstruct future paths, or create deadlocks. Its solvability and difficulty therefore depend on planning through an interconnected push-state space rather than isolated local decisions.
- Puzzle mechanics: Sokoban requires moving every box onto a designated target using only legal pushes, because boxes cannot be pulled.The player pushes one box at a time into an adjacent unoccupied space.
- Puzzle mechanics: A single box move changes board topology and player reachability, so an incorrect execution order can block paths or create deadlocks.Sequence is as important as destination, requiring a holistic plan over box interactions.
- Solvability: A push-based solver branches on box pushes and normalizes the player to its currently reachable region, avoiding redundant branches over individual player movements.Player steps relocate the worker without changing the puzzle, whereas pushes alter the puzzle state.
- Solvability: PSPACE-complete solvability can require searching an enormous state space because shortest solutions may be exponentially long and lack short verifiable certificates.Culberson established Sokoban’s PSPACE-completeness, distinguishing it from NP-complete puzzles with efficiently checkable certificates.
- Difficulty: Puzzle difficulty is measured by the number of push-state expansions before finding a solution, capturing search demand rather than state-space size.This machine-search measure is presented as an analogue of prior human-difficulty metrics, which did not significantly predict difficulty from global graph properties.
1.2 Masked diffusion model
Masked diffusion adapts diffusion to categorical Sokoban grids by replacing Gaussian noising with token masking and progressively revealing cells. Following MD4, the model trains with timestep-reweighted cross-entropy evaluated only at masked positions.
- Motivation: Discrete Sokoban cells cannot undergo Gaussian noising because walls, floors, and boxes have no meaningful intermediate states.Continuous image diffusion adds Gaussian noise, but categorical grid tokens lack sensible halfway states.
- Related work: Austin et al. formulate discrete diffusion as a categorical Markov chain without a score function, but use a more involved categorical ELBO than MD4.MD4 simplifies the masking case to ordinary cross-entropy.
- Training objective: MD4 reduces masked discrete diffusion training to timestep-reweighted cross-entropy computed only at masked positions.This project follows the MD4 training formulation directly.
- Masked diffusion: Masked diffusion replaces noising with hiding tokens behind a special [MASK] symbol, then progressively reveals cells from a fully masked grid.The schedule controls how many tokens are hidden, while diffusion steps determine how many cells are revealed per step.
- Sampling dynamics: Once a cell is unmasked, masked diffusion commits permanently to its predicted value and never samples that cell again.This differs from continuous diffusion, where every pixel is repeatedly nudged and early errors can be corrected later.
1.3 Contribution
The work trains a masked diffusion model on Boxoban tile completions alone, without solvers, rewards, or solvability labels, yet generates Sokoban puzzles that largely inherit the dataset’s solvability. The model achieves 77.4% unfiltered solvability, rising to 98.7% when single-wall repairs are counted, while its generated tile-pattern divergence tracks held-out puzzles.
- Method: Each puzzle is a 10×10 tile grid flattened into 100 tokens over seven tile types, plus a [MASK] symbol used during generation.The [MASK] symbol does not occur in the data.
- Results: 77.4% of generated puzzles are solvable unfiltered, rising to 98.7% when failures repairable by deleting one interior wall are counted.The evaluation generated and checked 50,000 puzzles; counting two-wall repairs leaves approximately 0.40% genuinely broken.
- Method: The model is trained only to fill masked cells, with no solver, reward, or solvability label in the training loop.Its formulation follows MD4, and the training data comes from DeepMind’s Boxoban dataset.
- Results: Generated-to-training tile-pattern divergence tracks held-out-to-training divergence at every sample size from 250 to 50,000, with a gap under 4% of the divergence itself.Both divergence series decay at the same rate, supporting the conclusion that solvability is inherited from the training dataset.
- Temperature sweep: Lowering τ from 1.0 to 0.6 raises solvability by 3.8 points, increases average wall count from 69.5 to 73.2, and cuts median solver effort by 36%.The corpus average wall count is 68.6, and τ = 1.0 is the setting matching real wall density.
2 Method and design choices
The method uses masked diffusion because Sokoban’s non-local constraints are poorly matched to fixed-order autoregressive generation. Its bidirectional Transformer reconstructs masked grid cells under a timestep-dependent objective, with design choices for weighting, diffusion length, and masking schedule.
- Model motivation: Diffusion reveals cells in arbitrary order, conditioning each prediction on all previously decided cells rather than a fixed prefix.This is intended to match Sokoban’s non-local interdependence across grid regions.
- Architecture: The generator is a bidirectional Transformer encoder with approximately 4.9M parameters, using 6 layers, 8 heads, width 1024, and dropout 0.1.Separate row and column embeddings provide the model with two-dimensional grid geometry.
- Training objective: At each sampled timestep, cells are independently masked with probability 1 − α_t under α_t = 1 − t/T and T = 100, and the model reconstructs the original masked tokens.The loss is computed at masked positions using timestep-dependent weighting.
- Diffusion steps: T = L = 100 uniquely pairs one revealed cell per sampling step with no unused trained timestep.Choosing fewer steps reveals multiple cells per step, whereas choosing more leaves trained timesteps unused by sampling.
- Noise schedule: w⋆(1) ≈8106 under cosine masking, versus w⋆(1) = T = 100 under linear masking.Cosine weighting diverges quadratically in 1/t, while linear weighting has a bounded ceiling equal to the sequence length.
3 Inference and evaluation
Inference reveals puzzles by repeatedly recomputing tile distributions while fixing uniformly selected cells, enabled by training on arbitrary masks. Evaluation finds high solvability, shallow one-wall failures, and no evidence of memorization.
- Inference: Generation starts from a fully masked 100-cell grid and fixes one sampled tile at a time across 100 steps.The model predicts all seven tile distributions simultaneously, samples candidates rather than using argmax, and never revises committed cells.
- Inference: Arbitrary-mask training enables any reveal order because the model learns pθ(c_i | c_S) for conditioning sets of every size and shape.This avoids directly modeling the full 100-cell joint distribution.
- Evaluation: 94.5% of unsolvable puzzles become solvable after deleting one interior wall, increasing effective solvability from 77.4% to 98.7%.The deleted walls received a median model probability of 0.45, compared with 0.93 for other interior walls in the same puzzles.
- Evaluation: Median nearest-neighbour distance is 12 for both generated and held-out puzzles, while exact reproductions are fewer in generated puzzles, 5 versus 19.The generated and held-out distributions have means 11.43 and 11.33, with 5.6% versus 7.5% within 5 cells, indicating no copying.
4 Conclusion
A masked diffusion model trained only on tile completion generates Sokoban puzzles that are 77.4% solvable without solvers, rewards, or solvability labels. The results suggest solvability is inherited from learned puzzle structure despite being a global, PSPACE-complete property.
- Conclusion: 77.4% of generated Sokoban puzzles are solvable unfiltered, despite training, sampling, and filtering using no solver, reward, or solvability label.Deleting one interior wall raises solvability to 98.7%, while allowing two-wall repairs leaves only ∼0.40% genuinely broken.
- Conclusion: Solvability is PSPACE-complete to decide and lacks a short certificate, yet emerges from an objective that only fills masked cells.The training objective never directly evaluates solvability.
- Conclusion: Generated puzzles match the training corpus’s structural divergence from held-out puzzles across sample sizes from 250 to 50,000, supporting inherited structure rather than trivial subset selection.The divergence stays within 4% of the held-out-versus-corpus divergence itself.
- Conclusion: Validation loss converges early while solvability keeps climbing, so stopping when loss flattens would forfeit roughly 25 points of solvability.Per-cell reconstruction loss is therefore not a proxy or stopping criterion for global structural properties.