Metraipolis › archive › dc_05cd7ed5dfd1

Solvable Sokoban Without a Solver via Diffusion — arXiv:2608.15958

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.15958
License (as archived): CC0-1.0
Archived: 2026-10-18T17:41:05.757Z
SHA-256 of the archived text: a324bf1cbdebd4362d88d49af38ffe1bb85e5ec133bdbbb7efc0aec06d27d13d
Stable URL of this page: https://metraipolis.com/documento/dc_05cd7ed5dfd1

How to cite

Solvable Sokoban Without a Solver via Diffusion — arXiv:2608.15958 — arXiv (en), https://arxiv.org/abs/2608.15958 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_05cd7ed5dfd1 (Metraipolis archive dc_05cd7ed5dfd1, sha256 a324bf1cbdebd4362d88d49af38ffe1bb85e5ec133bdbbb7efc0aec06d27d13d)

BibTeX

@misc{dc05cd7ed5dfd1,
  title = {Solvable Sokoban Without a Solver via Diffusion — arXiv:2608.15958},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.15958},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_05cd7ed5dfd1; sha256 a324bf1cbdebd4362d88d49af38ffe1bb85e5ec133bdbbb7efc0aec06d27d13d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.15958. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-18 in cs.AI).
Categorie arXiv: Artificial Intelligence (cs.AI) ; Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2608.15958 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T16:29:13.844Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).