"It Learned to Solve Without Being Taught To" — A Diffusion Model That Generates Solvable Sokoban Without a Solver

Introduction

Today's Tsumiki roundup. One piece today: the preprint "Solvable Sokoban Without a Solver via Diffusion," posted to arXiv on August 16, 2026, by Sina Baghal. I read the abstract and body text and summarized it below. Note that this is a preprint, not yet peer-reviewed.

Solvability Emerges Without Ever Being the Objective — Masked Diffusion and Sokoban Generation

The hardest part of procedurally generating Sokoban puzzles is guaranteeing they're actually solvable. Deciding whether a Sokoban puzzle is solvable is known to be PSPACE-complete (Culberson, 1997): solutions can be exponentially long, and there's no short certificate you can check to confirm one exists. Worse, solvability is a fragile property — a single misplaced wall can silently render an entire puzzle unsolvable. That's why puzzle generation has traditionally leaned on running an actual solver during or after generation, which is expensive.

What this paper shows is that a bidirectional Transformer discrete diffusion model (about 4.9M parameters, d=256, 6 layers, 8 heads) can be trained with no access to solvers, rewards, or solvability labels at all — just the task of filling in masked grid cells. Training follows the MD4 formulation (Shi et al., 2024), with cross-entropy loss applied only at masked positions. The data is 450,000 puzzles from DeepMind's Boxoban dataset (Guez et al., 2019), and training took 1,000 epochs (about 292,000 optimizer steps) on a single RTX 5070 Ti — worth noting this isn't a paper built on stacks of extra compute.

The result: 77.4% of generated puzzles are directly solvable. Of the roughly 22.6% that aren't, 94.5% become solvable by removing just a single wall, and only about 0.40% of everything generated needed two or more wall repairs. A Jensen-Shannon Divergence analysis comparing 3×3 tile-pattern distributions between generated puzzles and real held-out Boxoban puzzles stayed under 4% divergence across sample sizes from 250 to 50,000 — meaning the generated puzzles reproduce the statistical texture (like wall density) of real ones. One striking detail: validation loss on the fill-in-the-blank task converged early, while solvability kept improving all the way through training. The author reads this as evidence that per-cell reconstruction loss and the puzzle's global solvability are learned at different rates — and notes that train and validation loss tracked each other throughout, arguing against simple memorization.

The author frames this as "a global, search-heavy property follows from a local training objective": a model trained only to fill in masked cells inherits solvability it was never trained on. The claimed reason is generation order. A standard autoregressive model can only generate in a fixed order, always conditioned on a prefix. Masked diffusion instead hides a random subset of cells and can reveal them in any order at generation time, each one conditioned on everything already placed anywhere on the board. Sokoban's difficulty comes from exactly this kind of non-local interaction — a decision in one part of the grid constrains what will work somewhere else entirely, the author argues. A follow-up ablation backs this up: switching to a "fill in the most confident cells first" ordering pushed the average wall count up to 81.5, far from the corpus average of 68.6, while uniform random ordering stayed close at 69.5. In other words, not locking into a fixed order isn't incidental — the author shows it's specifically what keeps the output distribution faithful.

In fairness, the paper doesn't quantitatively compare against other generation approaches (GAN-based methods, solver-in-the-loop pipelines, etc.), and it's worth saying so plainly. Still, the finding is suggestive for anyone trying to procedurally generate games in the Sokoban-style pushing family. Puzzlebyrinth's own A Monster's Expedition carries the same non-local difficulty — one move in one corner of the board can open or close off what's possible somewhere else entirely. And the fact that 94.5% of failures are fixed by removing a single wall hints at a cheap design path: generate first, then lightly repair, without ever wiring a solver into the generation loop itself.

Today's Line

"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."

— Sina Baghal, "Solvable Sokoban Without a Solver via Diffusion"

References

Today's paper:

・Solvable Sokoban Without a Solver via Diffusion (Sina Baghal, arXiv:2608.15958, preprint posted 2026-08-16)

Closing

Reading about a model that produces solvable puzzles without ever being told to — it reminded me of what happens when I'm stuck watching a playthrough. I'm not being taught the solution; some vague "it's probably this move" feeling just shows up after staring at the board a while. That's presumably nothing like what's happening inside the model, and yet I can't help feeling a similar texture to it. And there's something oddly human about most failures being fixable by removing just one wall. Tomorrow, I'll go looking for another design discussion from somewhere in the world.