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

DOI10.1016/J.TCS.2018.04.031MaRDI QIDQ1637231zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Mikhail Rudoy

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

\((n^2 - 1)\)-puzzlecomplexity of gamesNP-hardnessrectilinear Steiner tree

Mathematics Subject Classification ID

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

Abstract: The 15 puzzle is a classic reconfiguration puzzle with fifteen uniquely labeled unit squares within a $4imes4$ board in which the goal is to slide the squares (without ever overlapping) into a target configuration. By generalizing the puzzle to an $nimesn$ board with $n^2-1$ squares, we can study the computational complexity of problems related to the puzzle; in particular, we consider the problem of determining whether a given end configuration can be reached from a given start configuration via at most a given number of moves. This problem was shown NP-complete in Ratner and Warmuth (1990). We provide an alternative simpler proof of this fact by reduction from the rectilinear Steiner tree problem.

Recommendations

• \textsc{Hanano} puzzle is \textsf{NP}-hard
• A real-time algorithm for the \((n^{2}-1)\)-puzzle
• Some provably hard crossing number problems
• A Simple Heuristic Proof of Hardy and Littlewood's Conjecture B
• Recognizing binary shuffle squares is \textsf{NP}-hard
• Easy NP-hardness Proofs of Some Subset Choice Problems
• scientific article; zbMATH DE number 3890729
• On the P vs NP question: a proof of inequality
• A simple proof of the \(A_{2}\) conjecture

Cites work

• A Modern Treatment of the 15 Puzzle
• A real-time algorithm for the \((n^{2}-1)\)-puzzle
• Games, puzzles, and computation
• scientific article; zbMATH DE number 2115805 (Why is no real title available?)
• On Steiner’s Problem with Rectilinear Distance
• Playing games with algorithms: algorithmic combinatorial game theory
• Swapping labeled tokens on graphs
• The \((n^ 2-1)\)-puzzle and related relocation problems
• The parallel search bench ZRAM and its applications
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(33)

• A real-time algorithm for the \((n^{2}-1)\)-puzzle
• How to solve the torus puzzle
• Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves
• Invitation to combinatorial reconfiguration
• Twenty years of progress of \(\mathrm{JCDCG}^3\)
• Computational complexity of jumping block puzzles
• Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard
• scientific article; zbMATH DE number 1529463 (Why is no real title available?)
• Permutation reconstruction from differences
• On the Symbolic Computation of the Hardest Configurations of the RUSH HOUR Game
• scientific article; zbMATH DE number 7765391 (Why is no real title available?)
• Computational complexity of jumping block puzzles
• Sequentially swapping tokens: further on graph classes
• Puzzle and dragons is hard
• Computational complexity of puzzles and related topics
• Additive approximation algorithms for sliding puzzle
• On the diameters of friends-and-strangers graphs
• Routing few robots in a crowded network
• Parameterized algorithms for coordinated motion planning: minimizing energy
• On the parameterized complexity of motion planning for rectangular robots
• Sequentially swapping tokens: further on graph classes
• Agent motion planning as block asynchronous cellular automata: pushing, pulling, suplexing, and more
• Reconfiguration of labeled matchings in triangular grid graphs
• On the complexity of finding central configurations of the graph-generalized ( n^2 - 1 )-puzzle
• Reconfiguration of labeled matchings in triangular grid graphs
• Routing few robots in a crowded network
• A minor-testing approach for coordinated motion planning with sliding robots
• On the parameterized complexity of motion planning for rectangular robots
• Parameterized algorithms for coordinated motion planning: minimizing energy
• Drainability and fillability of polyominoes in diverse models of global control
• The parameterized complexity of coordinated motion planning
• A characterization of achievable patterns of the MN-puzzle problem
• The \((n^ 2-1)\)-puzzle and related relocation problems

Describes a project that uses

Uses Software

• ZRAM

This page was built for publication: A simple proof that the \((n^{2} - 1)\)-puzzle is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1637231)