A simple proof that the \((n^{2} - 1)\)-puzzle is hard

DOI10.1016/j.tcs.2018.04.031zbMath1394.68159arXiv1707.03146OpenAlexW2735814871MaRDI QIDQ1637231

Mikhail Rudoy, Erik D. Demaine

Publication date: 7 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.03146

zbMATH Keywords

NP-hardnessrectilinear Steiner treecomplexity of games\((n^2 - 1)\)-puzzle

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Invitation to combinatorial reconfiguration ⋮ Sequentially swapping tokens: further on graph classes ⋮ Puzzle and dragons is hard ⋮ Computational complexity of jumping block puzzles ⋮ Unnamed Item ⋮ Computational complexity of jumping block puzzles ⋮ Twenty years of progress of \(\mathrm{JCDCG}^3\)

Uses Software

• ZRAM

Cites Work

• The \((n^ 2-1)\)-puzzle and related relocation problems
• A real-time algorithm for the \((n^{2}-1)\)-puzzle
• The parallel search bench ZRAM and its applications
• Swapping labeled tokens on graphs
• A Modern Treatment of the 15 Puzzle
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On Steiner’s Problem with Rectilinear Distance
• Unnamed Item
• Unnamed Item