# Solvable Sokoban Without a Solver via Diffusion

arXiv: https://arxiv.org/abs/2608.15958 · HTML: https://mlsanity.com/paper/2608.15958/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Discrete and text diffusion, one of 14 directions in Diffusion models.
- Builds on 5 of its 7 references that are in the map.
- First posted on arXiv 16 Aug 2026.

## Placed in

- Diffusion models / [Discrete and text diffusion](https://mlsanity.com/diffusion/discrete-and-text-diffusion/)

## Builds on (most cited first, 5 of 5)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024)
- [An investigation of model-free planning](https://mlsanity.com/paper/1901.03559/) (2019)

## Built on by (most cited first, 1 of 1)

- [Generative Models as Adaptive Trust Regions for Discrete Bayesian Optimisation](https://mlsanity.com/paper/2610.16992/) (2026)

## Abstract (arXiv)

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(ck mid c1 dots ck-1), meaning a fixed order, always conditioned on a prefix. Masked diffusion does not: it hides a random subset of cells and learns p(ck mid 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.