arXiv cs.AI· Zilai Wang·· 13 小时前AI 评分18
非局部水晶交换谜题的最优 93 步解法
An Exact 93-Move Solution to a Nonlocal Crystal-Exchange Puzzle
AI 导读
研究者为游戏 Order of the Sinking Star 的 11*11 水晶交换谜题给出了显式 93 条指令解法，并用精确代价有界广度优先搜索排除了所有更短解。搜索以 17 个占用格和 1 个活动格表示局面，最终保留 605,349,215 个占用集合与 1,863,925,136 个状态，构成该实例的计算机辅助证明，并附源码、执行日志与复现驱动。
正文 · 原文
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.
| Subjects: | Artificial Intelligence (cs.AI); Combinatorics (math.CO) |
| Cite as: | arXiv:2610.29493 [cs.AI] |
| (or arXiv:2610.29493v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2610.29493 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Zilai Wang [view email]
[v1]
Wed, 21 Oct 2026 09:49:13 UTC (39 KB)
来源：arXiv cs.AI · arxiv.org