A 93-Move Optimal Solution: An Exact Proof for a Nonlocal Crystal-Exchange Puzzle

The Puzzle and Its Rules

The crystal-exchange puzzle in Order of the Sinking Star challenges players to move all 16 crystals to their target positions on an 11×11 board using the fewest number of commands. A command swaps the player with the nearest crystal in the chosen row or column, regardless of distance; only an empty ray allows a normal unit to walk. Two doors let the player pass only once all 16 crystals are in place. This setup looks simple, yet the nonlocal nature of the commands—where the swap effect depends on the global arrangement—makes it extraordinarily complex.

Breadth-First Search (BFS) and cost-bounded search: BFS is a blind search strategy that expands states layer by layer in increasing order of steps (or cost), so the number of steps used when it first reaches the goal state is the minimum. Cost-bounded BFS adds an upper bound (93 in this case), expanding only states whose cost does not exceed that bound, and prunes with an admissible heuristic: if the lower bound on a state's cost plus the cost already spent exceeds the upper bound, the state is discarded. This guarantees completeness (no shorter solution is missed) while greatly reducing the search space.

Exact Solution and Excluding Shorter Solutions

The researchers provide an explicit 93-command solution and rule out all shorter solutions through an exact, cost-bounded breadth-first search (BFS). The search represents each position as 17 occupied cells (16 crystals plus the player) and one active cell. For efficient pruning, an admissible heuristic function is designed: it decomposes the command cost into a compressed core abstraction and residual movement, strengthened by necessary activation detours and corner-visit conditions.

The full computation retains 605,349,215 occupied sets and 1,863,925,136 states, ultimately proving that 93 moves is optimal. This is essentially a computer-assisted proof for a specific instance, accompanied by an explicit trust boundary for the implementation.

Admissible heuristic: In shortest-path search, a heuristic function estimates the minimum remaining cost from the current state to the goal state. If the estimate never overestimates the true cost, it is called "admissible." Admissibility is crucial: it guarantees that search algorithms (such as A* or cost-bounded BFS) will not mistakenly prune paths that contain the optimal solution. The heuristic in this article decomposes the command cost into a compressed core abstraction and residual movement, and adds activation detours and corner-visit conditions. All of these conditions are formally proven to ensure the estimate does not exceed the actual number of steps required, thereby achieving efficient pruning while preserving completeness.

Heuristic and Search Optimization

The core idea of the heuristic is to decompose the problem into two parts: a compressed core abstraction (capturing the global constraints of crystal exchanges) and residual movement (the player moving to a position where a swap can be executed). Through the "activation detour" condition, the search can identify that the player must first move to a specific position to activate certain swaps, thereby avoiding invalid branches. The corner-visit condition further prunes paths that cannot visit the necessary corners within the remaining steps.

These reductions and pruning conditions are all formally proven, ensuring the completeness of the search. The storage scheme is also carefully designed to handle the memory demands of billions of states.

Reproducibility and Trust Boundary

The authors provide source code, execution logs, and a reproduction driver so that the entire proof process can be independently verified. However, the reliability of a computer-assisted proof depends on the correctness of implementation details, so the authors explicitly state the trust boundary: the validity of the proof depends on the consistency between the code logic and the formal description. This transparency is essential for such complex search proofs.

Implications for Puzzle Design and AI Solvers

The significance of this work goes beyond solving a specific puzzle. It demonstrates how to transform nonlocal constraints into a tractable search problem and achieve exponential pruning through precise heuristic design. For game designers, this suggests that the depth of command-swap mechanics may far exceed surface appearances; for AI solver developers, this "abstraction + residual" heuristic construction approach can be transferred to other combinatorial optimization problems.

Moreover, the exact 93-move solution provides players with a theoretical optimal path, which may inspire the community to explore optimal solutions for more levels.

One-line Summary

Researchers present a 93-move optimal solution to the crystal-exchange puzzle and prove its optimality using cost-bounded BFS.

Paragraph Summary

This article explores the crystal-exchange puzzle on an 11×11 board in Order of the Sinking Star: players must move 16 crystals to their target positions using the fewest commands, where commands swap the player with the nearest crystal and have a nonlocal character. The researchers provide an explicit 93-move solution and rule out all shorter solutions through cost-bounded breadth-first search. The search retains over 600 million occupied sets and 1.8 billion states, achieving efficient pruning with an admissible heuristic (combining compressed core abstraction, residual movement, activation detours, and corner-visit conditions). This work is essentially a computer-assisted proof, and the authors provide source code, logs, and a reproduction driver while clarifying the implementation trust boundary. Finally, its implications for puzzle design and AI solvers are discussed.