The paper reports that A*, evolutionary, and reinforcement-learning search can solve 3D hypercube sliding puzzles, and that the stochastic methods find approximate solutions in dimensions 4 and 5 where A* times out.
Higher-dimensional cubical sliding puzzles
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We introduce higher-dimensional cubical sliding puzzles that are inspired by the classical 15 Puzzle from the 1880s. In our puzzles, on a $d$-dimensional cube, a labeled token can be slid from one vertex to another if it is topologically free to move on lower-dimensional faces. We analyze the solvability of these puzzles by studying how the puzzle graph changes with the number of labeled tokens vs empty vertices. We give characterizations of the different regimes ranging from being completely stuck (and thus all puzzles unsolvable) to having only one giant component where almost all puzzles can be solved. For the Cube, the Tesseract, and the Penteract ($5$-dimensional cube) we have implemented an algorithm to completely analyze their solvability and we provide specific puzzles for which we know the minimum number of moves needed to solve them.
fields
cs.AI 1years
2024 1verdicts
REJECT 1representative citing papers
citing papers explorer
-
Approximately Optimal Search on a Higher-dimensional Sliding Puzzle
The paper reports that A*, evolutionary, and reinforcement-learning search can solve 3D hypercube sliding puzzles, and that the stochastic methods find approximate solutions in dimensions 4 and 5 where A* times out.