Paper deep dive
Solvable Sokoban Without a Solver via Diffusion
Sina Baghal
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 8/22/2026, 3:22:23 AM
Summary
This paper demonstrates that a transformer-based discrete diffusion model, trained solely on tile completion (masked diffusion) without access to solvers, rewards, or solvability labels, can generate solvable Sokoban puzzles. The model achieves a 77.4% solvability rate, with an additional 94.5% of failures being repairable by removing a single wall. The authors argue that masked diffusion is structurally better suited for Sokoban than autoregressive models because it handles non-local interactions by revealing cells in random orders conditioned on the entire current state, rather than a fixed prefix. The model is trained on DeepMind's Boxoban dataset using an architecture adapted from MD4.
Entities (8)
Relation Signals (6)
Sina Baghal → authored → Solvable Sokoban Without a Solver via Diffusion
confidence 100% · Solvable Sokoban Without a Solver via Diffusion Sina Baghal
Sokoban → hascomplexity → PSPACE-complete
confidence 100% · Deciding whether a Sokoban puzzle is solvable is PSPACE-complete (Culberson, 1997)
Discrete Diffusion Model → trainedon → Boxoban
confidence 100% · the dataset is DeepMind’s Boxoban
Discrete Diffusion Model → achievesmetric → Solvability Rate
confidence 95% · achieves a solvability rate of 77.4%
Discrete Diffusion Model → adaptedfrom → MD4
confidence 90% · The training pipeline is adapted from MD4 (Shi et al., 2024)
Culberson → proved → Sokoban
confidence 90% · Culberson, 1997: solutions can be exponentially long... Deciding whether a Sokoban puzzle is solvable is PSPACE-complete
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.15958v1
- Canonical: https://arxiv.org/abs/2608.15958v1
Trouble viewing inline? Open PDF directly →
Full Text
33,634 characters extracted from source content.
Expand or collapse full text
Solvable Sokoban Without a Solver via Diffusion Sina Baghal Email: siinabaghal@gmail.com Abstract Deciding whether a Sokoban puzzle is solvable is PSPACE-complete [2]: 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(ck∣c1…ck−1)p(c_k c_1… c_k-1) meaning a fixed order and always conditioned on a prefix. Masked diffusion doesn’t: it hides a random subset of cells and learns p(ck∣any subset)p(c_k 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. As such, a generator that isn’t locked into a single fixed order is a better structural match for the problem than one that is. The figure below follows one generated puzzle across a single sampling run, from a fully masked grid to a finished board. The model only ever fills in masked cells; the finished board is solvable. The model’s training pipeline is adapted from MD4 [5], and the dataset is DeepMind’s Boxoban [3]. Both the trained model and instructions for generating puzzles are publicly available. AI usage. The research question, model architecture, training setup, and all experimental design decisions are the author’s; Claude Code was used as an implementation and editing assistant. 1 Preliminary This section is organized as follows. We first define the game of Sokoban, how a puzzle’s solvability is decided using a push-based solver, and how its difficulty is measured. We then describe the masked diffusion model: its mechanism, its evolution from the continuous-diffusion formulation, and its suitability for Sokoban puzzle generation. 1.1 Sokoban Sokoban is a single-player puzzle created in Japan around 1980. Played on a grid-based maze with a single character and multiple boxes, the objective is to move all boxes onto designated target positions. Game mechanics are strictly restricted to pushes, meaning that the player can only push one box at a time into an adjacent unoccupied space and cannot pull boxes. Due to spatial interdependencies, Sokoban cannot be decomposed into isolated tasks. Moving a single box alters board topology and player reachability; an incorrect execution order can obstruct future paths or render previously placed boxes into deadlocks. Sequence is therefore as vital as destination. Because localized, step-by-step decision-making fails, players must formulate a holistic plan accounting for all box interactions prior to execution. 1.1.1 Solvability A puzzle is solvable if some sequence of legal box pushes lands every box on a goal. We decide this with a push-based solver that branches on pushes, not on player moves. The player’s individual steps only relocate the worker without changing the puzzle, so branching on every movement would blow up the search with positions that differ solely in where the player stands. Instead we branch once per box push, and normalize the player to the region it can currently reach: every board with identical boxes and the player anywhere inside that reachable region collapses to a single search state. Branching is therefore tied to the box configuration rather than to navigation. We also prune dead cells: working backwards from each goal by pulling a box outward, any cell never reached is one no box could ever be pushed to a goal from, so pushes into it are discarded rather than branched on. Culberson [2] proved that deciding Sokoban solvability is PSPACE-complete. PSPACE is the class of problems solvable with a polynomial amount of memory, though possibly requiring exponential time, and it contains NP. What separates Sokoban from an NP-complete puzzle such as Sudoku is that its shortest solution can be exponentially long: there is no short certificate that a checker could verify quickly, so establishing that a puzzle is solvable may require searching an enormous state space. 1.1.2 Difficulty Jarušek and Pelánek [4] modeled Sokoban difficulty on the push-based state-space graph G=(V,E)G=(V,E), where each vertex v∈Vv∈ V is a game state (box positions plus the player’s reachable area) and each directed edge e=(u,v)∈Ee=(u,v)∈ E is a single valid box push. Evaluating metrics against large-scale human solving logs, they found that static, global properties of the graph fail to predict human difficulty: push-space size |V||V| showed no significant correlation (r=−0.11r=-0.11) and shortest push-solution length was only weakly predictive (r=0.30r=0.30). What did predict difficulty were metrics modelling the search a human actually performs, rather than properties of the finished graph. Two stood out. A decomposition metric, measuring how far a puzzle breaks into independent sub-problems that can be solved one at a time, reached ρ=0.82ρ=0.82 under Spearman correlation. A stochastic model of a human wandering the state space, rather than walking the optimal path, reached r=0.76r=0.76 under Pearson correlation. The difficulty measure used in this work is aligned with that finding. We rate a puzzle by the number of states the push solver expands before it finds a solution, which is a measure of how much search the puzzle demands rather than of how large its state space is. This is machine search rather than human search, so it is an analogue of Jarušek and Pelánek’s predictive metrics rather than one of them. It nonetheless falls on the same side of their distinction, and deliberately not on the side of |V||V|, which their logs show carries almost no signal. 1.2 Masked diffusion model Continuous diffusion models are built on a stochastic differential equation (SDE) that gradually turns data into noise. Song et al. [6] showed this process can be run in reverse in two ways: as a matching reverse-time SDE, or as a deterministic probability flow ODE with the same marginal distributions, i.e., an ordinary differential equation that a standard solver can integrate directly. Both routes need the same missing piece: the score function, ∇xlogpt(x) _x p_t(x), the gradient of the log-density of the noised data at each step. The score function has no closed form; it can only be estimated by training a separate network against a score-matching objective. Every part of this, meaning the SDE, the ODE, the gradient, the density is defined over a continuous, differentiable space. None of it has a meaning for discrete data: there is no gradient of a distribution over seven tile types, and no log-density of a word. Figure 1 shows the forward and reverse processes, and where the score function enters. Figure 1: Reproduced from Song et al. [6], Figure 1. Top, forward SDE: the process that corrupts data (0)x(0) into noise (T)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 ∇logpt() _x p_t(x), boxed in the equation, is known at every intermediate step. The diffusion models that generate images work on continuous data. The forward process gradually adds Gaussian noise to a picture until nothing is left but static; the model learns to run that backwards, removing a little noise at a time. Discrete data however breaks that. A Sokoban cell is a wall, or a floor, or a box; there is no “slightly noisy wall”, and nothing sensible halfway between a wall and a box. Gaussian noise has nothing to act on. Austin et al. [1] built a genuinely discrete diffusion process instead, replacing the SDE with a Markov chain over categorical transition matrices, with no score function required. However, the resulting training objective was still a fairly involved categorical ELBO. Shi et al. [5], in MD4: Simplified and Generalized Masked Diffusion for Discrete Data, showed that for the masking case, specifically, this collapses to something much plainer: an ordinary cross-entropy loss, computed only at masked positions and reweighted using the timestep. This project’s training algorithm follows the MD4 formulation directly. Masked diffusion replaces noising with hiding. Corruption means swapping a token for a special [MASK] symbol, and the schedule controls how many tokens are hidden rather than how much noise is added. Generation runs that backwards: start from a fully masked grid and progressively reveal cells, predicting what belongs in each. How many are revealed per step follows from the number of diffusion steps T, a design choice we return to in Section 2.3. In masked diffusion models commitments are final: once a cell is unmasked it can never be selected again, and the sampler only ever draws from cells still marked [MASK], so a wall placed at step 3 stays a wall for the rest of generation. Continuous diffusion has no such rule: every pixel is nudged at every one of its steps, all the way to the end, so an early bad direction can still be pulled back later. 1.3 Contribution We train a masked diffusion model to generate Sokoban puzzles, using the formulation from the MD4 paper [5]. The training data is DeepMind’s Boxoban [3] dataset. Puzzles here are 10×1010× 10 grids of tiles rather than sentences of words: each one flattens to 100 tokens over a vocabulary of 7 tile types (# wall, space floor, @ player, $ box, . goal, * box-on-goal, + player-on-goal), plus a [MASK] symbol the model uses but the data never contains. Figure 2 gives the tile key used throughout. Figure 2: Tile key. 1.3.1 Solvability emerges without supervision Trained only to fill in masked cells, with no solver, reward, or solvability label in the loop, the model generates puzzles that are 77.4% solvable unfiltered, rising to 98.7% once failures repairable by deleting a single interior wall are counted. Here 50,000 puzzles were generated using our model and every unsolvable puzzle was checked. Counting two-wall repairs as well, only ∼0.40% 0.40\% of everything generated is genuinely broken. Interestingly, the culprit walls were committed at a median probability of 0.45, against 0.93 for the other interior walls of the very same puzzles. 1.3.2 Distribution match The tile-pattern divergence between generated puzzles and the training corpus sits on the divergence between real held-out puzzles and the same corpus, at every sample size from 250 to 50,000, where the held-out split runs out. Both series decay at the same rate, and what separates them is under 4% of the divergence itself at every size. Solvability is simply inherited from the training dataset. 1.3.3 Temperature trade-off Lowering τ from 1.0 to 0.6 raises solvability by 3.8 points but inflates average wall count from 69.5 to 73.2 in the temperature sweep, against a corpus average of 68.6, while cutting median solver effort by 36%. The default τ=1.0τ=1.0 is the setting at which generated puzzles match real wall density. 2 Method and design choices This section lays out the design of the model and the reasoning behind each choice. We first motivate why a diffusion model, rather than an autoregressive one, suits Sokoban generation. We then describe the training objective and work through the three choices that shape it: the loss weighting that keeps every noise level contributing usefully, the number of diffusion steps, and the noise schedule. Each is presented not just as a setting but with the argument for why it takes the value it does. 2.1 Model choice The non-local interdependence between different parts of the puzzle is what makes it difficult, so an autoregressive generator, which commits to everything in one fixed order, isn’t a good fit for this kind of game. Diffusion does not work that way. It fills in cells in whatever order the reveal process happens to land on, and each new cell is conditioned on every cell already decided so far, wherever in the grid it sits, not on a fixed prefix that always runs in the same direction. The model might settle a goal in one corner, a wall on the opposite side, and only later the corridor connecting them, rather than reading the grid off in one fixed pass. Because a puzzle’s actual difficulty comes from exactly this kind of non-local interaction meaning a decision in one part of the grid constraining what will work somewhere else entirely, a generator that isn’t locked into a single fixed order is a better structural match for the problem than one that is. 2.2 Architecture The generator fθf_θ is a bidirectional Transformer encoder (≈ 4.9M parameters): d=256d=256, 66 layers, 88 heads, feed-forward width 10241024, dropout 0.10.1. Encoder only is used because the task is fill-in-the-blanks over a grid, not left-to-right generation. The generator maps a masked grid xt∈0,…,7100x_t∈\0,…,7\^100 and timestep t to per-cell logits over the 77 real tiles, fθ(xt,t)∈ℝ100×7f_θ(x_t,t) ^100× 7 ([MASK] is an input token only, never predicted). Cell i, at grid position (ri,ci)(r_i,c_i), is embedded as hi(0) h_i^(0) =Etok(xt,i)+Erow(ri)+Ecol(ci)+τ(t),τ(t)=MLP(sinusoid(t))∈ℝd. =E_tok(x_t,i)+E_row(r_i)+E_col(c_i)+τ(t), τ(t)=MLP (sinusoid(t) ) ^d. Here EtokE_tok, ErowE_row, and EcolE_col each maps an integer index to a learned d-vector. Separate row/column embeddings give attention the 2-D grid geometry directly rather than through a flat 1-D index. Moreover, sinusoid(t) (t) =[sin(tω0),cos(tω0),sin(tω1),cos(tω1),…],ωk=10000−2k/d. = [ (t _0), (t _0),\ (t _1), (t _1),\ … ], _k=10000^-2k/d. The sinusoidal form and the base 1000010000 are the standard ones introduced for positional encoding by Vaswani et al. [7] and carried over to diffusion timestep embeddings. Note that the timestep term τ(t)τ(t) is added identically to every cell. The embeddings then feed a stack of 6 standard pre-norm Transformer blocks (multi-head attention + FFN with residual connections), and a final linear layer projects each cell to logits over the 7 tiles. 2.3 Training At timestep t each cell is independently replaced by [MASK] with probability 1−αt1- _t, on a linear schedule αt=1−t/T _t=1-t/T with T=100T=100. At t=0t=0 the grid is intact; at t=Tt=T it is entirely mask. A training data point then consists of a sampled puzzle from the training data, a sampled t∈1,…,Tt∈\1,…,T\, and a masked version of the chosen puzzle via the scheduler. The model is then trained to recover the original tokens at the masked positions, where the loss is the cross-entropy weighted by w(t)=min(11−αt,wmax)=min(T/t,wmax),wmax=10.w(t)= \! ( 11- _t,\ w_ )= (T/t,\ w_ ), w_ =10. The loss function is therefore calculated as below. ℒ(θ)=x0,t,m[w(t)⋅1|M|∑i∈M−logpθ(x0(i)∣xt,t)],L(θ)=E_x_0,t,m [\,w(t)· 1|M| _i∈ M- p_θ (x_0^(i) x_t,t ) ], where m is the mask draw, with each position hidden independently with probability 1−αt1- _t, and M=i:mi=1M=\i:m_i=1\ is the set of positions it hides, where t∼Uniform1,…,Tt \1,…,T\. We now explain the three remaining choices: the weight cap, the number of diffusion steps, and the schedule. Weights. At timestep t only 100⋅t/T100· t/T cells are masked in expectation, so at t=1t=1 the model is graded on roughly one cell and at t=Tt=T on all hundred. Without reweighting, a step that hides a single cell contributes as much to the gradient as one that hides the entire grid. The 1/(1−αt)1/(1- _t) factor which falls out of the masked-diffusion ELBO restores the per-sequence scale. Note that t never reaches 00: there αt=1 _t=1, so nothing is masked, the loss has no positions to average over and w(t)w(t) is undefined, which is why t is drawn from 1,…,T\1,…,T\. The ratio T/tT/t is therefore largest at t=1t=1, where it reaches T, so with uncapped w(t)w(t) a single near-complete grid would carry T×T× the gradient weight of a fully-masked one, and the gradient becomes dominated by a handful of nearly finished examples. Small t is the near-complete regime, in which a grid has only a handful of cells left to fill. These are the cells that are critical for solvability. wmaxw_ therefore sets how much the model learns about the phase that determines the global property it is never trained on. Number of diffusion steps. Write L for the number of cells in a grid, so L=100L=100 here. Notice that T=LT=L is the unique value where, first, exactly one cell is revealed per step and, second, no trained timestep is left unused by the sampler. Every reveal-step must unmask at least one new cell, so sampling always runs min(T,L) (T,L) reveal steps. Choosing T<LT<L forces the sampler to reveal more than one cell per step; choosing T>LT>L leaves the sampler visiting only L of the T trained timesteps, so most are never used at inference. Scheduler. As mentioned above, since the loss is computed only at masked positions, a timestep with few masked tokens carries little information per gradient step, and the uncapped weight w⋆(t)≡1/(1−αt)w (t)≡ 1/(1- _t) compensates by amplifying it. The schedule decides how sharply this amplification grows as t approaches its minimum. Under the linear and cosine schedules, near t=0t=0 the masked fraction behaves as 1−αtlinear=tT,1−αtcosine≈π2t28T2,1- _t^linear= tT, 1- _t^cosine≈ π^2t^28T^2, i.e., a linear versus a quadratic falloff, so the uncapped weights grow as wlinear⋆(t)=Tt,wcosine⋆(t)≈8T2π2t2.w _linear(t)= Tt, w _cosine(t)≈ 8T^2π^2t^2. The cosine weight therefore diverges quadratically in 1/t1/t rather than linearly, reaching w⋆(1)≈8106w (1)≈ 8106 against linear’s w⋆(1)=T=100w (1)=T=100 which is a bounded ceiling equal to the sequence length itself. Finally, Algorithm 1 summarizes the training algorithm, following [5]. In Algorithm 1, training is shown for a single puzzle; the implementation vectorizes over a batch of B. Algorithm 1 Training step 1: Batch of puzzles x0(b)b=1B\x_0^(b)\_b=1^B, model fθf_θ 2: Sample t(b)∼Uniform1,…,Tt^(b) \1,…,T\ for each b 3: Compute αt=1−t/T _t=1-t/T 4: Sample masks mi∼Bernoulli(1−αt)m_i (1- _t) for each position 5: Create xtx_t: replace x0(i)x_0^(i) with [MASK] where mi=1m_i=1 6: Forward pass: logits=fθ(xt,t)logits=f_θ(x_t,t) 7: Average cross-entropy over the masked positions 8: Apply weight w(t)=min(1/(1−αt),wmax)w(t)= (1/(1- _t),\,w_ ) 9: Backpropagate and update θ 2.4 Loss and solvability The model was trained for 1,000 epochs over the 450,000-puzzle corpus, 292,000 optimizer steps at batch size 1,536, using AdamW (learning rate 2.45×10−42.45× 10^-4, weight decay 0.01, 125 warmup steps, cosine decay, gradient clipping at 1.0) in fp16 mixed precision on a single RTX 5070 Ti. Validation loss is measured every 1,000 steps on Boxoban’s held-out split, and solvability every 50,000 steps by generating 5,000 fresh puzzles from that checkpoint and running the push solver on each. Figure 3 shows all three. Loss converges early and then stays flat; solvability keeps climbing to the end of the run. The training objective is a per-cell reconstruction loss, while solvability is a global property it never sees, so the two are free to decouple. It is emphasized that a run halted when the loss flattened would have given up roughly 25 points of solvability. Train and validation loss also track each other throughout, so the long run is not overfitting. 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. 2.5 Distribution match To assess whether generated puzzles capture the structural style of the Boxoban corpus beyond mere solvability, we evaluate the Jensen-Shannon Divergence, defined as JSD(P∥Q)=12KL(P∥M)+12KL(Q∥M),M=12(P+Q),JSD(P Q)= 12KL(P M)+ 12KL(Q M), M= 12(P+Q), between the empirical 3×33× 3 sliding-window tile distributions of generated samples (Q) and the 450,000-puzzle training reference (P). Extracting 64 local 3×33× 3 windows per 10×1010× 10 grid captures critical structural features such as corridors, corners, and dead ends. We choose JSD over raw Kullback-Leibler divergence because it is symmetric, bounded in [0,1][0,1] under base-2 logarithms, and naturally handles unobserved patterns without requiring arbitrary additive smoothing. Finally, because sample size strongly affects support coverage and raw scores, every generated JSD score is calibrated directly against a baseline of real held-out puzzles evaluated at the identical sample size. Figure 4 compares generated puzzles against real ones on the same measurement: both series show how far a sample of puzzles diverges from the 450,000-puzzle training corpus in its distribution of local 3×33× 3 tile patterns, plotted against how many puzzles went into the sample. The validation set is Boxoban’s held-out split, which comes with DeepMind’s dataset and consists of 50,000 real puzzles that were never shown to the model. 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.59K^-0.59: the divergence a small sample shows is dominated by how few 3×33× 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. 3 Inference and evaluation This section reports the evaluation results for the trained model: solvability, one-wall repairability, memorization, and the effect of sampling temperature. We begin with sample puzzles (Figure 5), rated for difficulty by the push-based search described earlier. Below are the solutions to those puzzles (Figure 6). 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. 3.1 Sampling algorithm The generation process reverses corruption by starting with a 100-cell [MASK] grid and unmasking one cell at a time across 100 steps. At each step, the model predicts probability distributions over all seven tile types across the entire grid simultaneously. A candidate tile is sampled from each distribution—rather than selected via argmax—and exactly one uncommitted cell is chosen uniformly at random to be fixed. Discarding the remaining predictions and recomputing them from scratch on each step ensures the model chooses what tile to place while a uniform sampler determines which cell comes next. By conditioning each step on one additional finalized cell, the system bypasses having to model the full 100-cell joint distribution directly. In other words, the following holds P(c1,…,c100)=σ[∏k=1100P(cσ(k)∣cσ(1),…,cσ(k−1))],P(c_1,…,c_100)=E_σ [ _k=1^100P (c_σ(k) c_σ(1),…,c_σ(k-1) ) ], where σ is the random order in which cells happen to be revealed. Because training masks an arbitrary subset rather than a prefix, the model learns pθ(ci∣cS)p_θ(c_i c_S) for conditioning sets S of every size and shape, which is precisely what allows any reveal order to be used at sampling time. Selecting cells uniformly also avoids the pitfalls of confidence-based ordering: because walls are the easy, high-confidence majority class, committing high-confidence cells first biases subsequent predictions toward even more walls, inflating the average wall count in that comparison from 69.5, which matches the corpus average of 68.6, up to 81.5. Algorithm 2 provides the inference algorithm. Algorithm 2 Sampling 1: Trained model fθf_θ, T=100T=100 steps, temperature τ=1.0τ=1.0 2: Initialize x←[MASK]100x← [MASK]^100 3: for step=0,…,T−1step=0,…,T-1 do 4: Compute t=T−stept=T-step 5: Forward pass: p=softmax(fθ(x,t)/τ)p=softmax (f_θ(x,t)/τ ) for every cell 6: Draw a candidate tile for every cell: x^i∼Categorical(pi) x_i (p_i) 7: Collect the still-masked cells M=i:xi=[MASK]M=\i:x_i= [MASK]\ 8: Decide how many to reveal: n=max(⌈|M|/(T−step)⌉,1)n= ( |M|/(T-step) ,1 ), which is 11 here 9: Choose which cells to reveal: pick n of the masked cells in M at random, all equally likely 10: Commit the values sampled in line 5 at those cells (never revised afterwards) 11: end for 12: return x 3.2 One-wall fixes When a generated puzzle is unsolvable, the failure is usually shallow rather than structural: 94.5% of unsolvable puzzles become solvable by deleting a single interior wall, which lifts effective solvability from 77.4% to 98.7%. Each puzzle in Figure 7 displays the probability the model assigned that wall at the moment it committed it during generation. These probabilities have a median of 0.45, against 0.93 for the other interior walls of the very same puzzles. 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. 3.3 Memorization A generator that reproduced its training data would score well on every metric above while being worthless. For each generated puzzle we measure the Hamming distance to its nearest neighbour among the 450,000 training puzzles. This is equal to the number of the 100 cells on which the two grids differ, so 0 is an exact reproduction. The player’s position is canonicalised away before comparing. The worker moves freely within its reachable region, and the push solver collapses those positions into a single state for exactly that reason, so two grids differing only in where the worker stands are the same puzzle. Counting that as a difference would undercount duplicates. On its own, a distance of say 12 means little: every Boxoban puzzle shares the same wall border and similar density, so unrelated puzzles already might agree on most cells. We use the 50,000 held-out puzzles as the reference. They come from the same distribution but were never shown to the model, so they cannot have been memorised. We observe that they produce the same curve once compared against the training corpus. Over 50,000 generated puzzles and 50,000 held-out puzzles, the two distributions are near-identical: median distance 12 for both, mean 11.43 against 11.33. Exact reproductions are rarer in the generated set than in the real one, 5 against 19, as is close agreement, 5.6% within 5 cells against 7.5%. The model is therefore not copying; if anything it lands slightly further from the training corpus than genuine puzzles do. Figure 8 plots both distributions. 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. 3.4 Sampling temperature Temperature τ rescales the logits before each cell is drawn. Lowering it sharpens the distribution toward the model’s top choice; raising it flattens it. Figure 9 describes the impact of temperature on wall count and solvability. Figure 9: Solvability and average wall count against sampling temperature, 10,000 samples per setting on the T=100T=100 checkpoint. Shaded bands are 95% confidence intervals. The training corpus averages 68.6 walls per puzzle; sampling at τ=1.0τ=1.0 matches it, and every lower setting exceeds it. 4 Conclusion A masked diffusion model trained purely on tile completion, with no solver, reward, or solvability label at any point in training, sampling, or filtering, generates Sokoban puzzles that are 77.4% solvable unfiltered. Counting failures repairable by deleting a single interior wall raises this to 98.7%, and counting two-wall repairs leaves only ∼0.40% 0.40\% of generated puzzles genuinely broken. Solvability is a global property, PSPACE-complete to decide and with no short certificate to check, yet it follows here from an objective that only ever asks the model to fill in masked cells. Two checks argue that this is inherited rather than trivial or copied. The tile-pattern divergence between generated puzzles and the training corpus sits on the divergence between real held-out puzzles and that same corpus, at every sample size from 250 to 50,000 and to within 4% of the divergence itself, so the model reproduces the corpus structure rather than retreating to some easy subset of it. And nearest-neighbour Hamming distance rules out memorisation: generated and held-out puzzles give a median distance of 12 apiece, with exact reproductions rarer among generated puzzles than among real ones, 5 against 19. What the model has learned is the training distribution, and solvability comes with it. Two observations are worth carrying to other work of this kind. First, loss and solvability decouple: validation loss converges early and then stays flat while solvability keeps climbing to the end of the run, so a run halted when the loss flattened would have forfeited roughly 25 points of solvability. A per-cell reconstruction loss is not a proxy for a global structural property, and should not be used as a stopping criterion for one. Second, the failures that remain are shallow and the model half-signals them itself: the walls whose removal repairs a puzzle were committed at a median probability of 0.45, against 0.93 for the other interior walls of the very same puzzles. Last but not least, sampling temperature trades along the same axis, with τ=1.0τ=1.0 the setting at which generated wall density matches the corpus. References [1] Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. In Advances in Neural Information Processing Systems (NeurIPS), 2021. arXiv:2107.03006. [2] Joseph Culberson. Sokoban is PSPACE-complete. Technical Report TR97-02, Department of Computing Science, University of Alberta, 1997. [3] Arthur Guez, Mehdi Mirza, Karol Gregor, Rishabh Kabra, Sébastien Racanière, Théophane Weber, David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, Greg Wayne, David Silver, and Timothy Lillicrap. An investigation of model-free planning. In Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97 of PMLR, 2019. arXiv:1901.03559. Dataset: https://github.com/deepmind/boxoban-levels. [4] Petr Jarušek and Radek Pelánek. Difficulty rating of sokoban puzzle. Frontiers in Artificial Intelligence and Applications, 222:140–150, 2010. [5] Jiaxin Shi, Kehang Han, Zhe Wang, Arnaud Doucet, and Michalis K. Titsias. Simplified and generalized masked diffusion for discrete data. In Advances in Neural Information Processing Systems (NeurIPS), 2024. arXiv:2406.04329. [6] Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations (ICLR), 2021. arXiv:2011.13456. [7] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS), 2017. arXiv:1706.03762.