Comments on A087725 and the Fifteen Puzzle ========================================== From: Anton Kulchitsky <kulchits(AT)arsc.edu> Subject: sequence A087725 Date: Fri, 14 Aug 2009 12:02:54 -0800 Dear Dr. Sloane, I found the sequence A087725 online that tells about diameter of the graph of the fifteen puzzle for different configuration. I worked on this problem as a hobby in 1990s. You say that 2x3 puzzle has diameter of 21 and there is one only position (4 5 *)/(1 2 3). I can confirm this. However, I have some more solutions. The 2x4 puzzle has diameter of 36 and there is only one position at this depth from the initial position, namely ( 0 7 2 1 ) / ( 4 3 6 5 ) The 3x3 puzzle has diameter of 31 (you have it as a(3) number). There are only 2 position at this distance, namely (8 6 7)/(2 5 4)/(3 0 1) and (6 4 7)/(8 5 0)/(3 2 1) The 2x5 puzzle has diameter of 55 and 2 positions at that distance namely (0 9 3 7 1)/(5 4 8 2 6), (0 5 3 2 1)/(9 4 8 7 6) The 2x6 puzzle has diameter of 80, the same as 4x4 (!!!) and there are 2 positions at that distance (2002 result). They are (0 11 4 3 2 1)/(6 5 10 9 8 7) and (0 6 4 3 8 1)/(11 5 10 9 2 7) The 3x4 puzzle has diameter of 53 and 18 position at that distance. They are [1] 10 8 2 1 3 7 9 5 0 4 6 8 [2] 4 3 2 1 8 10 6 5 0 7 9 8 [3] 4 3 2 1 10 7 6 5 0 8 9 8 [4] 8 3 2 8 4 7 6 9 0 10 5 1 [5] 8 7 5 8 4 3 9 2 0 10 6 1 [6] 8 3 6 8 4 7 2 5 0 10 9 1 [7] 4 3 2 1 8 7 6 8 0 10 9 5 [8] 4 3 2 5 8 7 6 1 0 10 9 8 [9] 4 3 6 1 8 7 2 5 0 10 9 8 [10] 8 3 2 1 4 7 6 5 0 10 9 8 [11] 0 8 6 8 10 7 9 1 4 3 2 5 [12] 0 8 2 8 10 7 9 5 4 3 6 1 [13] 0 8 6 8 10 7 2 5 4 3 9 1 [14] 0 8 2 1 10 3 9 5 4 7 6 8 [15] 0 8 2 8 10 3 6 5 4 7 9 1 [16] 0 8 6 1 10 3 2 5 4 7 9 8 [17] 0 10 2 1 3 7 6 5 4 8 9 8 [18] 0 3 2 1 8 7 6 5 4 10 9 8 A very exact low estimate for the 2xN puzzle is (2N+1)*N = 1+2+3+...+2N (it is exact for 2x3, 2x4, 2x5 and differ by 2 with 2x6). All these results were obtained in 1998 (2x3 in 1997 by hand). I also have some interesting theorems that helps a lot in computations especially for 2xN puzzles. Finally, the program can generate solutions for not-rectangular games. The program used a modification of breadth-first search. I hope this information is useful for your project. Yours sincerely, Anton Kulchitsky Anton Kulchitsky, PhD HPC Specialist University of Alaska Fairbanks, Arctic Region Supercomputing Center West Ridge Research Building 909 Koyukuk Drive, Suite 105 PO Box 756020 Fairbanks, AK 99775-6020 Tel. (907)450-8689 Fax. (907)450-8603 E-mail: kulchits(AT)arsc.edu