From: "Erich Friedman" <efriedma@stetson.edu> Date: Sun, January 23, 2011 9:41 pm NeilB>> I'd very much like to know whether there is a harder 4x4 of either type. EF>surely a brute force search could answer this for 4x4 and smaller puzzles. though i bet 5x5 puzzles are going to be computationally expensive. not necessarily in solving a given puzzle, but in enumerating the possible puzzles! erich friedman Date: Tue, February 28, 2012 2:55 pm rwg> ... because I've already asked Funster Neil (who owes us his sliding block report) to figure it out for tomorrow. Neil has dutifully blogged it all at http://nbickford.wordpress.com/ At Erich's instigation, Neil did the brute-force search, taking about a cpu month, but with some bugs. He eventually got it down to a few hours and zero(?) bugs. "In the previous post I mentioned several methods that could be used to speed up the finding and exhaustive searching of sliding block puzzles, as well as a candidate for the ‘hardest’ one-piece-goal diagonal-traverse 4×4 sliding block puzzle. I am pleased to say that the various bugs have been worked out of the sliding block puzzle searcher, and that 132 has been confirmed to be the maximum number of moves for a simple simple simple 4×4 sliding block puzzle with no internal walls! (that’s not a lot of qualifiers at all)" I think it's remarkable that Neil found the 132 heuristically way beforehand. And the only solver I'm aware of is Corey Ziegler Hunts! (Rumor: also Nick Baxter?) In the summary picture<http://nbickford.files.wordpress.com/2012/01/best44.png>, note an apparent paradox: 11 pieces 64 moves 12 pieces 73 moves but the 12 piecer is just the 11 piecer with a domino cut in half! I'll spoil it only to the extent of revealing that the explanation is at http://nbickford.wordpress.com/2011/09/20/what-ive-been-working-on-lately/ --rwg