NJAS wrote:
I'm surprised that the 4x4 case hasn't been solved - can anyone help?
The fifteen puzzle is quite a bit harder than the Rubik's cube kind of puzzle, because it's not a group. The set of moves from a given position depend on where the blank is. Also, there is only two-fold symmetry to the puzzle, except in the variant where the home position of the blank is the center. There is also a variant in which sliding a row of tiles counts as a single move. I wrote a simple program to find the results for the eight-puzzle in all these variants (fancy search techniques are unnecessary for this size of problem). The answers I get are: Move Blank Maximum Number of maximal-distance positions and slide home distance (position of blank in those positions) tile corner 31 2 (adjacent edge) tile edge 31 2 (adjacent corner) tile center 30 148 (88 corner, 60 center) row corner 24 1 (center) row edge 24 2 (diagonally adjacent edge) row center 24 4 (corner) By the way, 16!/2 milliseconds is "only" about 331.5 years, and I'd guess the time taken to examine a position is probably more like a few dozen microseconds than a millisecond. But it's still cpu-years. Dan