# Maximum of minimum number of moves required for hardest 8 puzzle

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?

• What the heck is an "8 puzzle"???? – fleablood Mar 12 '18 at 18:40
• It's a variant of 15 puzzle for 3*3 Board en.wikipedia.org/wiki/15_puzzle – MessitÖzil Mar 12 '18 at 18:41
• 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? – Steven Stadnicki Mar 12 '18 at 18:46
• How did they find that number? – 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.