Approximately Optimal Search on a Higher-dimensional Sliding Puzzle
Nono SC Merleau, Miguel O’Malley, Érika Roldán, Sayan Mukherjee · 2024
Read Approximately Optimal Search on a Higher-dimensional Sliding Puzzle by Nono SC Merleau, Miguel O’Malley, Érika Roldán, Sayan Mukherjee (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01937.txt.
Description
Four authors take a sliding puzzle off the chessboard and onto a hypercube. Colored rings sit on the corners of a d-dimensional cube, and the task is to slide each ring to its matching corner. A move is legal only when a whole face of a set size is empty, a rule that generalizes how pieces collide. Finding the fewest moves is God's algorithm territory, and even the classic 15-puzzle resists fast exact answers.
The team benchmarked three solvers: exact A-star search, an evolutionary method, and reinforcement learning. All three cracked the three-dimensional puzzle at every setting. As dimensions rose, A-star fell away, while the two learners still found routes with a median under 30 moves. The evolutionary method ran fastest but rarely found the true minimum at the top dimensions.
Catalog record
| CREATOR | Nono SC Merleau, Miguel O’Malley, Érika Roldán, Sayan Mukherjee |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-01937