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?
$\begingroup$
$\endgroup$
1
asked Oct 5, 2014 at 12:16
-
1$\begingroup$ Do you mean the maximum of all of the possible minimum number of moves? $\endgroup$– LeppyR64Oct 5, 2014 at 16:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
answered Oct 5, 2014 at 17:13