Solvable Sokoban Without a Solver via Diffusion

Sina Baghal

cs.AIAug 16, 2026

Solvable Sokoban Without a Solver via Diffusion

Authors: Sina Baghal

Abstract

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.

Figures & tables

Figure 1: Reproduced from Song et al. [ 6 ] , Figure 1. Top, forward SDE: the process that corrupts data $\mathbf{x}(0)$ into noise $\mathbf{x}(T)$ , shown corrupting a photograph step by step. Bottom, reverse SDE: the same process run backwards, turning noise back into data. This is made possible only if the score function $\nabla_{\mathbf{x}}\log p_{t}(\mathbf{x})$ , boxed in the equation, is known at every intermediate step.

Figure 3: Training and validation loss (left axis) against solvability (right axis) over the training run. Solvability is measured on 5,000 freshly generated puzzles per checkpoint.

Figure 4: Tile-pattern JSD against the 450,000-puzzle training corpus, plotted against sample size, for generated puzzles and for real held-out puzzles measured identically. Both series decay as $K^{-0.59}$ : the divergence a small sample shows is dominated by how few $3\times 3$ patterns it can cover, not by the source it was drawn from. The held-out curve is therefore the floor, and the generated curve sits on it.

Figure 5: Nine puzzles generated from a fully masked grid, sampled at six points across the 100 denoising steps. One cell is committed per step in uniformly random order and never revised; cells still showing M are masked. Verdicts and push counts appear in the final panel, once every cell is committed, and the bars rate each puzzle against the training corpus’s difficulty quartiles.

Figure 6: The same nine puzzles, played back under solutions found by the push-based solver, sampled at six points through the playback. The solver is run only for evaluation and plays no part in generation.

Figure 7: Nine unsolvable puzzles, each repaired by deleting one interior wall. The red outline marks the removed cell and the chip gives the probability the model assigned it when it was committed during generation. Measured on 11,288 unsolvable puzzles from a 50,000-sample run.

Figure 8: Nearest-neighbour Hamming distance to the training corpus, player position canonicalised away. Blue: for each of 50,000 held-out puzzles, the distance to its nearest neighbour among the 450,000 training puzzles. Orange: the same measurement for 50,000 generated puzzles. The blue series is the reference: it is what a generator that memorised nothing would score. Mass piled up near zero in the orange series would be memorisation; there is none.

Figure 9: Solvability and average wall count against sampling temperature, 10,000 samples per setting on the $T=100$ checkpoint. Shaded bands are 95% confidence intervals. The training corpus averages 68.6 walls per puzzle; sampling at $\tau=1.0$ matches it, and every lower setting exceeds it.

Procedural Content Generation

Procedural content generation creates game levels, 3D worlds, assets, stories, and simulation environments through algorithms and learned models.

See all 66 papers

Sep 1, 2026

Diffusion as a Training Curriculum for Timestep-Free Iterative Reasoning

Diffusion models and recursive reasoners are both iterative, but they carry information across iterations differently. We add a persistent hidden state to a diffusion denoiser and remove its timestep conditioning, leaving a single shared update that can be run to arbitrary depth. The result is an anytime solver: accuracy keeps improving with inference depth far beyond the rollout lengths and backpropagation window used in training, reaching 99.90% exact solve on Sudoku-Extreme. We also obtain 98.93% solve rate on Maze-Unique. Surprisingly, progressive denoising is unnecessary at inference: holding corruption at its maximum by replacing every non-clue variable with fresh Gaussian noise at each step retains near-perfect solving and converges to stable solutions. This simple noise-injection mechanism enables a single trajectory to efficiently explore the solution space and settle on the correct answer without parallel rollouts, candidate selection, or external verifiers required by prior reasoning models. Nonetheless, ordered annealed corruption remains critical during training, which suggests that diffusion's primary contribution to our anytime solver is not a sampling procedure at inference, but a denoising training curriculum.

Mariia Drozdova, Aidan Sirbu, Pietro Miotti +4

Google, Paradigms of Intelligence Team · University of Geneva · School of Computer Science, McGill University +4

Constraint Satisfaction Algorithmic Reasoning Diffusion Models

Ask PDF

Oct 7, 2026

Think Before You Paint: Recursive Latent Reasoning for Diffusion Models

Diffusion models generate realistic images but often fail on visual reasoning tasks, such as filling in a Sudoku or drawing the path through a maze. When a discrete symbolic representation is available, recursive methods such as the Tiny Recursive Model (TRM) solve even hard instances of these puzzles. We ask how such reasoning can be carried over to pixels, where no symbolic representation is available. We propose Painter-Thinker (PaTh): a small recursive network (the Thinker) reasons over a grid of learned tokens that encode the noisy image and the conditioning, refines a latent state within every denoising step, and steers a frozen diffusion model (the Painter) through ControlNet adapters. The Thinker is trained with the standard reconstruction loss alone, without symbolic targets, a solver, or a verifier. PaTh solves 92.5% of hard MNIST Sudoku puzzles (prior best 75%) and 71.2% of extreme ones (prior best 4.1%), with 10M parameters against 82M for a standard diffusion model. It also improves on mazes, Queens, and CLEVR scenes with specified spatial relations, and its advantage grows with problem size. Diagnostic experiments show that PaTh recovers from injected mistakes that the diffusion model cannot repair, especially when many cells are wrong. Together, these results show that reasoning mechanisms developed for symbolic data can be integrated into pixel-space diffusion without symbolic supervision, opening a path toward generating data under increasingly complex constraints.

Paweł Skierś, Małgorzata Grzanka, Wojciech Masarczyk +2

Warsaw University of Technology · IDEAS Research Institute · University of Amsterdam

Latent Visual Reasoning Diffusion Models Constrained Generative Modeling Pixel-Space Diffusion Models

Ask PDF

Oct 20, 2026

Binary Discrete Diffusion: Candidate-Set Diffusion for Logic and Planning Tasks

Discrete diffusion models iteratively denoise a noisy sequence of categorical data such as text, enabling any-order generation with self-correction and in-filling capabilities. This makes them promising candidates for reasoning, planning, and constrained-generation tasks like coding and math. Yet masked and uniform diffusion erase a token's identity in a single corruption event, so their noisy states cannot explicitly represent partially resolved uncertainty in which several alternatives remain plausible. We close this gap with Binary Discrete Diffusion, a family of continuous-time discrete-diffusion processes whose noisy state is a set of candidate tokens per position, represented as a binary membership vector. Binary diffusion changes candidate sets through additions and removals, allowing information to be lost and recovered gradually while the diffusion state itself represents partial uncertainty. On Sudoku-Extreme, Boxoban, and graph coloring, the symmetric formulation of binary diffusion consistently outperforms strong, well-tuned masked and uniform baselines under matched architectures and controlled training, sampling, and tuning budgets, with its largest gains on the hardest instances, while remaining competitive on language modeling (Text8, TinyStories, OpenWebText). These results support candidate sets as an effective intermediate representation for iterative reasoning and show that the corruption kernel can materially change the computation learned by the reverse model.

Rodrigo Casado Noguerales, Dimitri von Rütte, Bernhard Schölkopf +2

ETH Zurich · Max Planck Institute for Intelligent Systems · ELLIS Institute Tübingen

Diffusion Models Diffusion-Based Planning Masked Diffusion Models

Ask PDF

Abstract

Procedural Content Generation

Explore similar work

Diffusion as a Training Curriculum for Timestep-Free Iterative Reasoning

Think Before You Paint: Recursive Latent Reasoning for Diffusion Models

Binary Discrete Diffusion: Candidate-Set Diffusion for Logic and Planning Tasks