Solvable Sokoban Without a Solver via Diffusion

In the world of computer science, there is a class of problems so complex that checking a solution can be easy, but finding one requires navigating a maze of possibilities so vast it would take longer than the age of the universe to solve by brute force. These are not merely difficult puzzles; they are problems where the path to the answer is not just long, but exponentially long, meaning that every step you take can open up a universe of new possibilities while simultaneously closing off others. One of the most famous examples of this is a game called Sokoban, played on a grid where a single character must push boxes onto specific target squares. The catch is that the character can only push, never pull, and once a box is wedged into a corner, it is often stuck forever. Because the position of one box can completely alter the reachability of the entire board, the game cannot be broken down into small, independent tasks. Solving it requires a holistic plan that accounts for every interaction before a single move is made. For decades, the ability to generate new, valid puzzles of this kind has been a challenge, because creating a solvable maze is just as hard as solving one, and checking if a maze works usually requires a powerful computer to simulate every possible move.

A recent study has found a surprising way to generate these complex puzzles without ever teaching the computer how to solve them. Researchers trained a type of artificial intelligence model to fill in missing pieces of a Sokoban grid, much like a human completing a crossword puzzle by guessing the missing words based on the surrounding letters. The model was shown thousands of real puzzles and asked to learn the patterns of walls, floors, and boxes, but it was never told which puzzles were solvable, nor was it given any rewards for creating a working game. It simply learned to predict what tile should go in a hidden spot based on the tiles already visible. The result was startling: when the model generated new puzzles from scratch, 77.4 percent of them were solvable. This is a remarkable outcome because the model was never explicitly trained to ensure solvability; it was only trained to fill in the blanks. The researchers found that the ability to create a solvable puzzle was not a separate skill the model learned, but a natural byproduct of learning the local patterns of the game.

The success of this approach relies on how the model thinks about the grid. Traditional computer programs that generate sequences, like those that write text, work in a fixed order, deciding the first word, then the second, then the third. This linear approach struggles with Sokoban because a decision made at the very beginning of the grid can constrain what is possible at the very end, creating a conflict that the program cannot fix later. The model used in this study, however, does not follow a fixed order. It starts with a completely empty grid where every cell is hidden and reveals them one by one in a random sequence. At each step, it looks at the entire board as it currently stands—walls here, boxes there, and empty spaces elsewhere—and decides what belongs in the next hidden spot. This allows the model to place a wall in one corner and a goal in the opposite corner, and then figure out the corridor that connects them, adjusting its understanding of the whole board with every new piece it reveals. This flexibility mirrors the way a human player must think about the game, where the difficulty comes from the non-local interactions between distant parts of the board.

To test how well this method worked, the researchers generated 50,000 new puzzles and checked each one with a standard solver. They found that nearly three-quarters of the puzzles were solvable immediately. Even more telling was what happened to the puzzles that failed. In 94.5 percent of the unsolvable cases, the puzzle could be fixed simply by removing a single interior wall. This suggests that the model was not just guessing randomly; it was creating structures that were almost entirely correct, with only minor, shallow errors preventing a solution. The researchers also checked to ensure the model was not simply memorizing the puzzles it had seen during training. They compared the new puzzles to the original dataset and found that the generated puzzles were just as different from the training data as real, unseen puzzles were. The model had learned the underlying structure of the game, not just a list of specific examples.

The study also explored how the model's behavior changed when the researchers adjusted its confidence. By making the model more decisive in its choices, they could increase the solvability rate to nearly 99 percent, though this came at the cost of creating puzzles with slightly more walls than usual. The default setting, however, produced puzzles that matched the density of walls found in the original training set perfectly. This balance between structure and randomness is key. The model learned that for a puzzle to be valid, the walls and boxes must fit together in a very specific way, and by learning to fill in the gaps correctly, it inadvertently learned the rules of solvability. The researchers noted that the model's performance on the global property of solvability kept improving long after its ability to predict individual tiles had stopped getting better. This indicates that the two goals are distinct: a model can be good at filling in a single tile without being good at creating a whole puzzle, but in this case, mastering the local details was enough to unlock the global solution.

The implications of this finding extend beyond just making better puzzles. It demonstrates that complex, global properties can emerge from simple, local training objectives. The model was never told that a puzzle must be solvable, yet it learned to create them anyway. This suggests that the structure of the data itself contains the logic of the solution, and that a model capable of understanding the relationships between all parts of a system can inherit the ability to solve it. The researchers confirmed that the model was not using a hidden solver to guide its generation. Every step of the process was driven by the model's own predictions based on the visible parts of the grid. The fact that the model could generate a solvable maze without ever seeing the solution path is a testament to the power of learning the patterns of a system deeply enough to reproduce its most difficult properties.

In the end, the work shows that the barrier between generating a problem and solving it is not as high as previously thought. By training a model to simply complete a pattern, the researchers unlocked the ability to create valid, complex challenges. The model did not need to be a grandmaster of the game to create a game worth playing; it only needed to understand the rules of the tiles. This approach offers a new way to think about artificial intelligence, suggesting that if we teach a system to understand the local relationships within a complex world, it may naturally learn to navigate the global challenges of that world without ever being explicitly taught how to do so. The puzzles generated were not perfect, but they were close enough that a tiny adjustment could make them work, proving that the model had grasped the essence of the game.