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

07/11/2017
by   Erik D. Demaine, et al.
0

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 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset