A few minor nits on the 15 puzzle. I've always seen the puzzle discussed as "half the arrangements are reachable", and simply assumed it was the even permutations of the sliding pieces that were reachable. I was trying to write down a mapping from the (nonnegative) integers < 16!/2 to the reachable positions and ran into trouble. The mapping to even permutations of [1,16] is easy enough, but a tiny problem appears. [I'm calling the blank space 16 here.] If the blank is in the last position (lower right corner, assuming standard reading order for the cells), then the piece to the left can be moved into the blank cell. This is a swap, which switches an even permutation to an odd one and vice versa. The truth appears to be that indeed, exactly half the positions are reachable, but the description is more complicated. Suppose we color the puzzle cell positions with a checkerboard of black and white squares. The a position is achievable iff it's an even permutation and the blank is at a black square, or if it's an odd permutation and the blank is at a white square. Still 50%, but the mapping rule for the integers will need a little fixup. --- Second nit. The "max solution is 80" paper doesn't tell us the graph diameter, but only that all nodes are within distance 80 of the starting position. (Along with giving 2 of the furthest- from-start positions.) I think we can say that the diameter is at most 82, since a position with the blank in a central or edge position can be morphed into the initial position in one or two moves (plus a relabeling of the tiles). Redoing the search with an initial position where the blank is on the edge and getting a final answer of 79 would prove diameter 80. --- The group of positions for Rubik's is much bigger than 16! But solving individual positions in the rigorous minimum number of moves is feasible now, and has been for a while, since you can work from both Start and Goal towards the middle, and there are only around 10^10 middle positions. If we were lucky, a similar situation might apply to the 15 puzzle, with only about sqrt(16!/2) ~= 3 million positions being reachable in 40 moves. I have no idea if this is true. --- 10^13 positions can be represented as a bit table (reachable in <=K steps, or maybe exactly K steps). That's only 1.25 TB. A lot of storage, but 100GB disks are cheaply available. --- Wechsler's solution algorithm (his note 4, with three lists) can be simplified slightly for the 15 puzzle, since each move changes the color of the "blank square". The reachable positions can be subdivided exactly into two equinumerous classses, those with the blank on a black square (which are reachable in an even number of moves), and those with the blank on a white square (which are an odd distance from Start). When discarding positions reachable from the Current List, only the Previous and Next Lists need be examined; they are of opposite color to the Current List. A good encoding of positions can give considerable locality for the 1-neighbor operator, so the implied sorting step for uniquing the 1-neighbors of the Current List is tractable. --- During the 15-puzzle craze (1880?) there were published problems with prizes and best-found solutions. I wonder if anyone has compared these answers to "truth". Rich rcs@cs.arizona.edu