A Simple Sokoban Puzzle Just Stumped Every AI Model

A deceptively simple Sokoban puzzle — the classic box-pushing game — has exposed a surprising blind spot in today's most advanced AI systems. Despite billions of parameters and state-of-the-art reasoning capabilities, not a single AI model has managed to solve a basic configuration featuring just 4 boxes and 4 target positions.

The challenge, which has been circulating in AI research and developer communities, involves moving boxes labeled 1 through 4 onto corresponding target points labeled 5 through 8. It is the kind of puzzle a human player might crack in minutes, yet GPT-4o, Claude 3.5 Sonnet, Gemini, and other leading models have all failed to produce a correct solution.

Key Takeaways

• A standard Sokoban puzzle with 4 boxes and 4 targets has defeated every major AI model tested
• Models including GPT-4o, Claude, and Gemini all failed to reach a valid solution
• The failure highlights fundamental weaknesses in spatial reasoning and multi-step planning
• Sokoban is classified as an NP-hard problem in computational complexity theory
• Current LLM architectures lack true internal world-simulation capabilities
• The gap between language fluency and logical problem-solving remains enormous

Why Sokoban Is Harder Than It Looks

Sokoban, originally created by Japanese game designer Hiroyuki Imabayashi in 1981, is a transport puzzle where players push boxes around a warehouse grid to place them on designated storage locations. The rules are brutally simple: you can only push a box, never pull it, and you can only push one box at a time.

What makes the game devilishly difficult is its computational complexity. Sokoban has been proven to be PSPACE-complete, meaning the difficulty of solving it grows exponentially with the size of the puzzle. Even small configurations can require dozens of precise moves where a single wrong push can render the puzzle unsolvable.

Unlike chess or Go, where AI systems like AlphaZero have achieved superhuman performance, Sokoban demands a different kind of intelligence. It requires the solver to maintain a persistent mental model of the entire grid, simulate future states across many moves, and recognize irreversible mistakes before making them.

How AI Models Fail at the Puzzle

The failures observed across multiple AI platforms follow remarkably similar patterns. When presented with the Sokoban configuration, models typically exhibit several types of errors:

• Spatial confusion: Models lose track of where boxes and walls are located after just 2-3 moves
• Illegal moves: AI frequently suggests pushing a box through a wall or moving through occupied spaces
• Deadlock blindness: Models push boxes into corners or against walls, creating unsolvable states without recognizing the mistake
• Circular reasoning: Some models enter loops, repeating sequences of moves that return to a previous state
• Premature victory declarations: Models occasionally announce success when boxes are clearly not on their target positions

These failures are not edge cases or prompt engineering issues. Multiple users have tested various prompting strategies — including step-by-step instructions, coordinate systems, visual ASCII representations, and chain-of-thought prompting. None have yielded a correct solution.

The core issue is architectural. Large language models process information as sequences of tokens. They do not maintain an internal spatial grid or simulate physical interactions. When an LLM 'reasons' about a Sokoban puzzle, it is essentially pattern-matching against training data rather than truly simulating the game state.

The Spatial Reasoning Gap in Modern AI

This Sokoban failure is not an isolated incident — it reflects a well-documented weakness in current AI architectures. Research from institutions including MIT, Stanford, and DeepMind has repeatedly shown that LLMs struggle with tasks requiring persistent state tracking and spatial manipulation.

A 2024 study published by researchers at Google DeepMind found that even the most capable language models scored below 30% on spatial reasoning benchmarks that human participants solved with over 90% accuracy. The gap is particularly wide in tasks that require:

• Maintaining and updating a 2D or 3D mental model
• Planning sequences of more than 5-7 dependent steps
• Recognizing irreversible actions and avoiding them proactively
• Understanding physical constraints like gravity, collision, and containment

Compared to AlphaZero's mastery of chess and Go, which relied on dedicated tree-search algorithms and reinforcement learning in simulated environments, LLMs have no equivalent mechanism for exploring and evaluating spatial problem spaces. AlphaZero played millions of games against itself to develop intuition. LLMs, by contrast, learned language patterns from text — a fundamentally different kind of knowledge.

The Sokoban challenge also stands in stark contrast to the impressive performance LLMs have shown on standardized tests, coding challenges, and even mathematical proofs. These successes can create a misleading impression of general intelligence when, in reality, the models excel primarily in domains well-represented in their training data.

Why This Matters for the AI Industry

The implications of this failure extend far beyond a puzzle game. Spatial reasoning and multi-step planning are critical capabilities for many real-world AI applications that companies are actively pursuing.

Consider the following use cases that depend on the same cognitive skills Sokoban tests:

• Robotics: Warehouse robots need to navigate spaces, move objects, and avoid creating blockages — essentially real-world Sokoban
• Autonomous driving: Self-driving cars must predict and plan through complex spatial scenarios with irreversible consequences
• Supply chain optimization: Logistics planning requires moving goods through constrained networks with sequential dependencies
• Architecture and design: AI-assisted building design demands understanding spatial relationships and physical constraints
• Game development: AI agents in video games need to solve spatial puzzles and navigate complex environments

Companies like Amazon, Tesla, and Boston Dynamics are investing billions in AI systems that must operate in physical space. If current AI architectures cannot solve a 4-box Sokoban puzzle on a simple grid, it raises serious questions about their readiness for the messy complexity of the real world.

This does not mean these applications are impossible — but it suggests that hybrid approaches combining LLMs with specialized spatial reasoning modules, physics engines, or reinforcement learning systems will likely be necessary.

What Researchers Are Doing About It

The AI research community has not ignored this class of problems. Several promising approaches are being explored to bridge the spatial reasoning gap.

Neurosymbolic AI, which combines neural networks with symbolic reasoning systems, has shown promise on planning tasks. By maintaining an explicit, structured representation of the problem state alongside a neural network's pattern-matching abilities, these hybrid systems can track spatial configurations more reliably.

World models — a concept championed by Meta's chief AI scientist Yann LeCun — aim to give AI systems an internal simulator that can predict the consequences of actions before taking them. LeCun has argued that current LLMs are fundamentally limited because they lack this kind of predictive world model, and his team at Meta's FAIR lab is actively building architectures designed to address this gap.

Reinforcement learning approaches, similar to those used in AlphaZero, have already solved Sokoban at superhuman levels. DeepMind's earlier work demonstrated that purpose-built RL agents could solve complex Sokoban levels by learning through millions of trial-and-error attempts. The challenge now is integrating these capabilities into more general-purpose AI systems.

OpenAI's o1 and o3 reasoning models represent another angle of attack, using extended 'thinking time' to work through complex problems step by step. However, early reports suggest that even these enhanced reasoning models struggle with spatial puzzles, indicating that more thinking time alone may not be sufficient without the right underlying representation.

Looking Ahead: When Will AI Crack Spatial Reasoning?

The Sokoban challenge serves as a humbling reminder that artificial general intelligence remains a distant goal. While LLMs have made extraordinary progress in language understanding, code generation, and even mathematical reasoning, spatial intelligence represents a frontier that current architectures are poorly equipped to conquer.

Industry experts suggest several milestones to watch for in the coming 12-24 months. The integration of spatial reasoning benchmarks into standard AI evaluations could push model developers to prioritize this capability. The emergence of multimodal models that combine vision, language, and planning may also help bridge the gap, as visual processing naturally encodes spatial relationships.

For now, the simple Sokoban puzzle stands as an elegant litmus test — a reminder that intelligence is multifaceted, and that mastering language is only one piece of a much larger puzzle. The next time an AI chatbot impresses you with a eloquent essay or a complex code snippet, remember: it probably cannot push 4 boxes onto 4 dots.

That gap between linguistic brilliance and spatial competence may well define the next great challenge in artificial intelligence research.