Minimum 93-move solution found for complex crystal-exchange puzzle
An Exact 93-Move Solution to a Nonlocal Crystal-Exchange Puzzle
Artificial Intelligence
Summary
This paper solves a tricky puzzle game where a player must swap places with crystals on a board and reach an exit with specific conditions. The puzzle involves commands that move the player by swapping positions with crystals along rows or columns. The authors found the shortest exact sequence of 93 moves needed to win this game and proved that no shorter solution exists. They used a detailed computer search method that carefully tracked all possible game states and moves, supported by clever rules to reduce the search space. The result is a computer-verified proof including all steps and code used.
What this means in practice
- •For game developers: Design puzzle levels with guaranteed minimum step solutions using computer-assisted exact search methods demonstrated here.
- •For robotic path planners: Apply search techniques balancing abstraction and detailed state tracking to optimize commands in complex movement environments.
Authors
Zilai Wang
Abstract
We determine the minimum number of directional commands needed to solve alevel of Order of the Sinking Star, modeled as a crystal-exchangepuzzle on an 11*11 board. A command swapsthe player with the nearest crystal in the selected row or column, regardlessof distance; only an empty ray permits an ordinary unit walk. Two gates admitthe player to the exit exactly while all sixteen crystals occupy their targetcells. We give an explicit 93-command solution and exclude every shortersolution by an exact, cost-bounded breadth-first search. The search representsa position by its seventeen occupied cells and one active cell. Its admissibleheuristic partitions command costs between a compressed core abstraction andresidual motion, strengthened by a necessary activation detour and a cornervisit condition. The completed computation retained 605,349,215 occupied setsand 1,863,925,136 states. We prove the reductions and pruning conditions,describe the exact storage scheme, and provide source code, execution logs,and a reproduction driver. The result is a computer-assisted proof for thespecified instance, with an explicit implementation trust boundary.