FEATURED ESSAY · 2026-09-07
"It Learned to Solve Without Being Taught To" — A Diffusion Model That Generates Solvable Sokoban Without a Solver
One piece today: the preprint "Solvable Sokoban Without a Solver via Diffusion" (Sina Baghal), posted to arXiv on August 16, 2026. Deciding whether a Sokoban puzzle is solvable is PSPACE-complete, so puzzle generation has traditionally relied on expensively running an actual solver. This paper trains a Transformer-based discrete diffusion model with no access to solvers, rewards, or solvability labels — just the task of filling in masked grid cells — and finds that 77.4% of generated puzzles are directly solvable, with 94.5% of the rest fixable by removing a single wall. It explains the mechanism through generation-order flexibility: a global property (solvability) leaking out of a purely local training objective.
