1. I'm willing to bet a moderate amount of money that Michie's MI group did not compute the diameter of the 15-puzzle in the 1960s. 2. The puzzle doesn't have all that much exploitable symmetry. 3. Dan: you can turn it into a group, in a way, whose elements are the permutations that leave the empty square where it started. For the 15-puzzle, I can see a fairly simple set of nine generators, made up of 4, 6, 8, 10, or 12 atomic moves. I don't know how much this would help; I guess I'm hoping for some sort of theoretical insight. Cough it up, dude. 4. If you have lots of space, the obvious algorithm is a brute force breadth-first exploration of the entire puzzle. Berlekamp, Conway, and Guy did this, apparently by hand, for some sliding-block puzzles including the classic "Dad's Puzzle", in WW. In this kind of search, you maintain three lists of positions: the Previous list, the Current list, and the Next list. All the positions in each list are at the same remoteness from Solved. You take each position on the Current list and enumerate its neighbors. Those neighbors that are not found in any of the three lists are added to the Next list. When all the positions in the Current list have been considered in this fashion, you discard the Previous list, and make the Current list Previous, the Next list Current, and the new Next list empty. This algorithm is initialized by having the Previous list empty, the Current list containing only Solved, and the Next list empty. The n-th major iteration leaves the Next list populated by all positions at remoteness n from Solved. 5. If you don't have enough space to store the fattest layer (and believe me, you don't; it almost certainly requires terabytes), there are various tricks that allow you to save space at the cost of speed. 6. Interesting progress could be made in one of two ways: tricks that make it very fast to process a single position, and tricks that allow you to process fewer positions. I'd be fascinated to hear of any insight that might permit this computation to be done in less than a decade. -A