I have read that the hardest 8 puzzle requires 31 steps to solve, i.e. every solvable 8 puzzle can be solved in max. 31 steps. How is that?

  • 2
    $\begingroup$ What the heck is an "8 puzzle"???? $\endgroup$ – fleablood Mar 12 '18 at 18:40
  • $\begingroup$ It's a variant of 15 puzzle for 3*3 Board en.wikipedia.org/wiki/15_puzzle $\endgroup$ – MessitÖzil Mar 12 '18 at 18:41
  • $\begingroup$ What do you mean by 'how is that' here? How did they find that number? How is it not smaller? How would you compute the number for a larger puzzle? $\endgroup$ – Steven Stadnicki Mar 12 '18 at 18:46
  • $\begingroup$ How did they find that number? $\endgroup$ – MessitÖzil Mar 12 '18 at 18:47

The wikipedia link for the 15 puzzle points to an OEIS link which points to a paper "Complete Solution of the Eight-Puzzle .." by Alexander Reinefeld. (The link in the OIES page is bad.) The distribution of solution lengths and the maximum length 31 were obtained by exhaustively evaluating all $9!/2$ configurations.


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.