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