Baghal: a model that never tried to solve anything drew solvable Sokoban 77.4% of the time — Fukai Reads

In short — solvable boards, without ever calling a solver

When you ask a machine to generate Sokoban levels — the puzzle where you push crates onto marked squares — the expensive part is not drawing the board. It is checking that the board can actually be finished. The normal recipe is to run a solver on every candidate and throw away the ones that fail. This manuscript does that check never, not once, during generation.

The only thing the model was trained to do is fill in blanks. Hide a random subset of the cells of a 10×10 board and ask what belongs in the hidden ones. No solver, no reward, no solvable/unsolvable label. And yet 77.4% of the boards it produced turned out to be solvable.

Of the remainder, 94.5% become solvable by deleting a single interior wall, which brings the effective figure to 98.7%. The author frames it as a global, search-heavy property emerging from a purely local training objective. For a designer, the practical content is that the verification step moves rather than disappears.

Who wrote it, and what kind of paper it is

The author is Sina Baghal, writing alone. The arXiv record lists no institutional affiliation, so the name is all I will assert here.

It is posted on arXiv as arXiv:2608.15958, submitted on 16 August 2026, primary category cs.AI, cross-listed to cs.GT and cs.LG. No conference or journal is named. In other words this is a preprint, not a peer-reviewed paper, and its numbers should be read on that footing. It has also not been widely discussed yet.

I picked it because the quietly expensive part of making puzzles is verification. Drawing a board is fast. Proving that the board can be finished can cost many times more than drawing it, depending on the genre. Anything that moves that cost is close to implementation.

It is also small. About 4.9 million parameters, trained on a single GPU. This is not a result that needs a research lab's compute to reproduce, which is part of why it caught my eye.

Why solvability is the wall that level generators hit

Deciding whether a Sokoban board can be finished is PSPACE-complete (Culberson, 1997). The manuscript spells out why that bites: solutions can be exponentially long, and there is no short certificate — no compact proof a third party could check quickly.

So generation usually becomes a loop: draw a board, hand it to a solver, discard it if the solver fails. The higher the discard rate, the more of your generation budget is really solver time. Cut that and the whole pipeline changes character.

The training data is DeepMind's Boxoban (Guez et al., 2019), 450,000 puzzles. Every board is a 10×10 grid over seven tile types — wall, floor, player, box, goal, box-on-goal, player-on-goal — so a board is simply a sequence of 100 cells.

For difficulty the manuscript counts the number of states a push-based solver — one that branches on pushes rather than on player steps — expands before it finds a solution. On how that relates to human difficulty, it cites Jarušek and Pelánek, where decomposition-based metrics reached ρ=0.82 and stochastic search models reached r=0.76.

The method: teach nothing but blank-filling

The generator is a masked diffusion model. Diffusion usually brings to mind adding noise to an image, but nothing is blurred here. Cells are replaced by a [MASK] symbol, and the schedule controls how much is hidden rather than how much noise is added. The formulation follows MD4 (Shi et al., 2024).

Training is plain. Take one of the 450,000 boards, hide each cell independently with some probability, and ask the model to name the true tile in every hidden cell. The hiding fraction follows a linear schedule over 100 steps. Since a board has 100 cells, that works out to roughly one cell per step.

What matters is that the order is not fixed. A left-to-right model, like one writing a sentence, can only ever condition on the cells before the one it is filling. Masked diffusion is trained to answer given any subset of the remaining cells. Sokoban is a genre where one wall on one edge can decide whether the opposite corner is a dead end, so the author argues this order-free conditioning fits the problem.

The model is small: a bidirectional Transformer encoder of about 4.9M parameters, width 256, 6 layers, 8 heads. Each cell embedding simply adds row, column and step information; there is no exotic machinery. Training ran 1,000 epochs over the corpus, 292,000 optimizer steps at batch size 1,536, in mixed precision on a single RTX 5070 Ti.

One small detail does real work: the loss weighting. A nearly complete board — only a handful of cells still hidden — would otherwise carry an enormous share of the gradient, so the weight is capped (at 10 in the manuscript). As the author notes, that cap also decides how much the model learns from exactly the late-stage boards where solvability is settled.

Generation runs the other way. Start from a fully masked grid and commit one cell per step across 100 steps. The cell to commit is chosen uniformly at random each time. Committing the most confident cells first would front-load walls and inflate the average wall count from 69.5 to 81.5. Once a cell is committed it is never revised.(Diagram) How generation runs: from a fully masked grid, one cell is committed per step in random order until the board is complete. No solver runs at any point.

77.4%, and 98.7% after one wall

The headline result is that 77.4% of generated boards were solvable. One naturally wants to know what that is high relative to, but as far as I could read, the manuscript does not put a competing generator in a comparison table. The number has to be taken on its own.

Of the failures, 94.5% became solvable by deleting a single interior wall, which lifts the effective figure to 98.7%. Counting repairs of up to two walls, only about 0.40% of everything generated is genuinely broken. Most failures are not structural collapse; they are one blocked corridor.

The interesting part is that the model appears to have doubted those very walls. The culprit walls were committed at a median probability of 0.45, against 0.93 for the other interior walls of the same puzzles. The numbers come from 11,288 unsolvable boards out of a 50,000-sample run.(Diagram) Deleting one interior wall lifts solvability from 77.4% to an effective 98.7%. The culprit walls had been committed at a median probability of just 0.45.

Resemblance to real boards is measured too. Each grid is cut into 64 overlapping 3×3 windows, the distribution of tile patterns is collected, and its divergence from the 450,000-puzzle corpus is computed. Generated boards and held-out real boards both close that gap as sample size to the power −0.59. In the author's framing, the held-out curve is the floor, and the generated curve sits on it.

Turning the sampling temperature down from 1.0 to 0.6 raises solvability by 3.8 points, but the average wall count rises from 69.5 to 73.2 against a corpus average of 68.6, so the boards drift away from real ones. At the same time, median solver effort drops by 36%. In plain terms, tightening the dial moves you toward easier, wallier, less authentic boards.

One more practical finding concerns when to stop training. Validation loss flattens early, yet solvability keeps climbing to the end of the run. The manuscript puts it bluntly: a run halted when the loss flattened would have given up roughly 25 points of solvability. For anyone building their own generator, that may be the most useful sentence in the paper.

What a puzzle maker can take home

First, read it as shrinking verification rather than removing it. If you are running a Sokoban-like level generator, you can re-budget the solver on the assumption that 77 of every 100 candidates pass untouched, moving from 'solve everything' to 'investigate only what fails'.

Second, implement 'delete one wall' as a repair move. Instead of discarding a failed board, add a post-process that removes each interior wall in turn and re-checks. Under this manuscript's conditions that alone rescued 94.5% of failures. The habit — one more move before the bin — transfers to other genres.

Third, use the model's own confidence to find suspect cells. Record the probability at which each cell was committed and try repairs in order of doubt. Culprit walls sat at a median of 0.45 against 0.93 for the rest. With a gap that wide you do not need to try every cell.

Fourth, treat temperature as a difficulty dial. Turning it to 0.6 yields easier boards but more walls and a flatter look. You might tighten it for tutorials and return to 1.0 later. Do look at the output, though: numbers can improve while players simply see 'more of the same level'.

Fifth, do not let loss decide when to stop training. Measure the share of usable boards periodically and keep going until that stops improving. In this manuscript the gap between the two stopping rules was about 25 points.

Sixth, the scale. About 4.9M parameters on one GPU is within reach of a solo developer or a hyper-casual team. If you are planning to mass-produce levels with a small team, it is worth weighing a blank-filling model trained on your own boards before renting something enormous.

What we do not know

Start with the constraints that are simply structural. The work is confined to Boxoban's format: 10×10 boards with four boxes. Whether the same thing happens at other sizes, or under rules other than Sokoban, cannot be read off this manuscript. Generation is a fixed 100-step procedure with no mechanism for revising a committed cell.

The author is explicit about one design cost: the cap on the loss weight. Capping it limits how much the model learns from nearly complete boards — and the few cells placed at that late stage are exactly the ones that decide solvability. The author describes the cap as setting how much the model learns about the phase that determines the global property it is never trained on. The 77.4% should be read together with where that dial sits.

There is also a memorization check. For each generated board it measures the Hamming distance to its nearest neighbour among the 450,000 training puzzles — how many of the 100 cells differ, with 0 meaning an exact reproduction — after canonicalising the player's position away. I could read the design of that check but not its resulting numbers in the original, so I will not quote figures for it here.

What follows is what Fukai would point out. First, solvable is not the same as good. The manuscript rates generated boards against the corpus's difficulty quartiles, but there is no evaluation with human players. Prior work relating solver effort to felt difficulty is cited (ρ=0.82 and so on); this generator's own output was not tested on people.

Second, the comparisons are thin. I found no experiment placing this method beside, say, a left-to-right generator to see what solvability rate that yields. Whether 77.4% is a win for the method or a property of Boxoban as material is hard to separate from this manuscript alone.

Third, it is a preprint: not peer-reviewed, single-authored, with no replication yet. The right reading is 'under these conditions, this was observed', not 'diffusion models can generate solvable levels' as a general law.

How Fukai reads it

I would place this work not in the race to generate more, but in the design question of where verification lives. Most writing about generative AI for level design competes on making more complex things. Here the generator got no smarter; the checker simply had less to do. A dull blank-filling objective, solved without a fixed commit order, produced consistency between distant parts of the board as a by-product. In the vocabulary of design criticism, this is closer to automating the consistency check than to automating the rules. If that reading holds, the next question is not accuracy but operations: where does a team draw the line for shipping a level it never verified?

What to read next to see the map

For how handcrafted and generated levels divide the work, our own Handcrafted versus generated levels is the map. On making a generated level's dead ends visible to the player, Legible failure goes deeper. If you want the feel of a pushing puzzle in your hands, start from A Good Snowman Is Hard To Build or Patrick's Parabox.

Around the source itself, three works make the borrowing visible: MD4 (Shi et al., 2024) for the generative skeleton, Boxoban (Guez et al., 2019) for the data, and Culberson (1997) for the complexity result. Reading them in the order Culberson → Boxoban → MD4 → this manuscript is the gentlest path.

Sources

Papers and materials referenced in this article:

・Solvable Sokoban Without a Solver via Diffusion (Sina Baghal, 2026, arXiv preprint, not peer-reviewed)

・Related work: Simplified and Generalized Masked Diffusion for Discrete Data (Shi et al., 2024, NeurIPS 2024) — the MD4 formulation this manuscript follows

・Dataset: Boxoban Levels (Guez et al., DeepMind, 2019) — the 450,000 puzzles used for training

・Background: Joseph Culberson, "Sokoban is PSPACE-complete" (1997) — the classic result on the complexity of deciding solvability