

A089473


Number of configurations of the sliding block 8puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.


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;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

The sequence was first provided by Alexander Reinefeld in Table 1 of "Complete Solution of the EightPuzzle..." (see corresponding link in A087725) with a typo "749" instead of "748" for a(12).


REFERENCES

For references and links see A087725.


LINKS

Table of n, a(n) for n=0..31.
Hugo Pfoertner, FORTRAN program to solve small sliding block puzzles.
Hugo Pfoertner, Table of solution lengths of the 8puzzle
I. Kapustik, Cesta.
J. Knuuttila, S. Broman and P. Ranta, nPuzzle, in Finnish (2002).
A. Reinefeld, Complete Solution of the EightPuzzle and the Benefit of Node Ordering in IDA*. Proc. 13th Int. Joint Conf. on Artificial Intelligence (1993), Chambery Savoi, France, pp. 248253.
Takaken, nPuzzle 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 ... 31


PROG

See link.


CROSSREFS

Cf. A087725 = maximum number of moves for n X n puzzle, A089474 = 8puzzle starting with blank square at center, A089483 = 8puzzle starting with blank square at midside, A089484 = solution lengths for 15puzzle, A090031  A090036 = other sliding block puzzles.
Sequence in context: A067945 A309263 A166156 * A118021 A326312 A134162
Adjacent sequences: A089470 A089471 A089472 * A089474 A089475 A089476


KEYWORD

fini,full,nonn


AUTHOR

Hugo Pfoertner, Nov 19 2003


STATUS

approved



