Comments on A087725 and the Fifteen Puzzle
==========================================
From: Anton Kulchitsky
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