5
$\begingroup$

You know, that puzzle where 1 slot in a four-by-four square is open and you slide the fifteen remaining blocks around to make a picture. What's the maximum amount of moves required to complete it, if you got the worst position possible?

$\endgroup$
  • 1
    $\begingroup$ Do you mean the maximum of all of the possible minimum number of moves? $\endgroup$ – LeppyR64 Oct 5 '14 at 16:12
8
$\begingroup$

For larger versions of the n-puzzle, finding a solution is easy, but the problem of finding the shortest solution is NP-hard. For the 15-puzzle, lengths of optimal solutions range from 0 to 80 single-tile moves or 43 multi-tile moves.

And for the 24-puzzle:

In 2011, a lower bound of 152 single-tile moves had been established; current established upper bound is 208 single-tile moves or 109 multi-tile moves.

http://en.wikipedia.org/wiki/15_puzzle#Solvability

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.