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?
1 Answer
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.