Jud McCranie sent in this sequence to the OEIS: %I A087725 %S A087725 0,6,31 %N A087725 Maximum number of moves required for the n X n generalization of the Fifteen Puzzle. %C A087725 a(4) >= 66, a(5) >= 114. a(3) is from Reinefeld, using the method of Korf. The lower bounds on a(4) and a(5) are from Korf and Korf & Taylor, and are unlikely to be tight. %D A087725 Richard E. Korf, Depth-First Iterative-Deeping: An Optimal Admissible Tree Search, Artificial Intelligence, 27(1), 97-110, 1985. %D A087725 Richard E. Korf and Larry A Taylor, Finding Optimal Solutions to the Twenty-Four Puzzle, Proceedings of the 11th National Conference on Artificial Intelligence, 756-761, 1993. %H A087725 Richard E. Korf, <a href="http://citeseer.nj.nec.com/cache/papers/cs/4003/http:zSzzSzwww.cs.ucla.eduzSz~ltaylorzSztwentyfour.pdf/korf96finding.pdf">Home Page</a> %H A087725 Alexander Reinefeld, Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*, International Joint Conference on Artificial Intelligence, pp. 248-253, 1993. <a href="http://www.ams.org/notices/200004/fea-hales.pdf">Reinefe H A087725 Alexander Reinefeld, <a href="http://www.ams.org/notices/200004/fea-hales.pdf">Home Page</a> %H A087725 Eric Weisstein, <a href="http://mathworld.wolfram.com/15Puzzle.html">15 Puzzle in MathWorld</a> %e A087725 All solvable configurations of the Eight Puzzle on a 3x3 matrix can be solved in 31 moves or fewer, and some configurations require 31 moves, so a(3)=31. %Y A087725 Cf. A046164. %Y A087725 Adjacent sequences: A087722 A087723 A087724 this_sequence A087726 A087727 A087728 %K A087725 hard,nonn,bref,nice %O A087725 0,2 %A A087725 Jud McCranie (j.mccranie(AT)adelphia.net), Sep 30 2003 I'm surprised that the 4x4 case hasn't been solved - can anyone help? NJAS