# A simple proof that the (n2-1)-puzzle is hard

arXiv: https://arxiv.org/abs/1707.03146 · HTML: https://mlsanity.com/paper/1707.03146/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2017.

## Built on by (most cited first, 3 of 3)

- [The Parameterized Complexity of Coordinated Motion Planning](https://mlsanity.com/paper/2312.07144/) (2023)
- [On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles](https://mlsanity.com/paper/2312.10887/) (2023)
- [The Fifteen Puzzle- A New Approach through Hybridizing Three Heuristics Methods](https://mlsanity.com/paper/2302.02985/) (2023)

## Abstract (arXiv)

The 15 puzzle is a classic reconfiguration puzzle with fifteen uniquely labeled unit squares within a 4 × 4 board in which the goal is to slide the squares (without ever overlapping) into a target configuration. By generalizing the puzzle to an n × n board with n2-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.