这篇论文用扩散模型搞出了能生成可解推箱子的办法，不用求解器，成功率77.4%，失败的大多拆一面墙就能救回来，而且开源可用。
判断推箱子谜题是否可解是 PSPACE-complete 问题（Culberson, 1997），解可能指数级长。研究者用基于 transformer 的离散扩散模型，仅训练瓷砖补齐任务，不访问求解器或可解性标签，生成谜题的可解率达 77.4%。剩余失败中 94.5% 只需移除一面墙即可变为可解。该模型基于 MD4 训练管线，使用 DeepMind 的 Boxoban 数据集，代码与生成指令已公开。
Solvable Sokoban Without a Solver via Diffusion
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.