|
Search: id:A089473
|
|
|
| A089473 |
|
Number of configurations of the sliding block 8-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners. |
|
+0
14
|
|
| 1, 2, 4, 8, 16, 20, 39, 62, 116, 152, 286, 396, 748, 1024, 1893, 2512, 4485, 5638, 9529, 10878, 16993, 17110, 23952, 20224, 24047, 15578, 14560, 6274, 3910, 760, 221, 2
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
The sequence was first provided by Alexander Reinefeld in Table 1 of "Complete Solution of the Eight-Puzzle..." (see corresponding link in A087725) with a typo "749" instead of "748" for a(12).
|
|
REFERENCES
|
For references and links see A087725.
|
|
LINKS
|
Hugo Pfoertner, FORTRAN program to solve small sliding block puzzles.
Hugo Pfoertner, Table of solution lengths of the 8-puzzle
I. Kapustik, Cesta.
J. Knuuttila, S. Broman and P. Ranta, n-Puzzle, in Finnish (2002).
A. Reinefeld, Complete Solution of the Eight-Puzzle and the Benet of Node Ordering in IDA*. Proc. 13th Int. Joint Conf. on Artificial Intelligence (1993), Chambery Savoi, France, pp. 248-253.
Takaken, n-Puzzle Page.
Takaken, No. 33 (8 puzzles).
|
|
EXAMPLE
|
From the starting configuration
123
456
78-
the two final configurations requiring 31 moves are
647 ... 867
85- and 254
321 ... 3-1
|
|
PROGRAM
|
See link.
|
|
CROSSREFS
|
Cf. A087725 = maximum number of moves for n X n puzzle, A089474 = 8-puzzle starting with blank square at center, A089483 = 8-puzzle starting with blank square at mid-side, A089484 = solution lengths for 15-puzzle, A090031 - A090036 = other sliding block puzzles.
Sequence in context: A125508 A067945 A166156 this_sequence A118021 A134162 A045776
Adjacent sequences: A089470 A089471 A089472 this_sequence A089474 A089475 A089476
|
|
KEYWORD
|
fini,full,nonn
|
|
AUTHOR
|
Hugo Pfoertner (hugo(AT)pfoertner.org), Nov 19 2003
|
|
|
Search completed in 0.002 seconds
|
