A090031 Number of configurations of the 5 X 5 variant of sliding block 15-puzzle ("24-puzzle") that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

1, 2, 4, 10, 26, 64, 159, 366, 862, 1904, 4538, 10238, 24098, 53186, 123435, 268416, 616374, 1326882, 3021126, 6438828, 14524718, 30633586, 68513713, 143106496, 317305688, 656178756, 1442068376, 2951523620, 6427133737, 13014920506, 28070588413, 56212979470, 120030667717

Offset

0,2

Comments

The 15-block puzzle is often referred to (incorrectly) as Sam Loyd's 15-Puzzle.

Sum of sequence terms = A088020(5)/2.

152 <= (number of last sequence term) <= 205 (see A087725 and cube archives link for current status). - Hugo Pfoertner, Feb 12 2020

References

See A087725 for references.

Links

Table of n, a(n) for n=0..32.

Robert Clausecker, term generator puzzledist.c

Robert Clausecker, The Quality of Heuristic Functions for IDA*, Zuse Institute Berlin (2020).

Hugo Pfoertner, Configuration counts for n*n sliding block puzzles.

Tomas Rokicki, comment in Twenty-Four puzzle, some observations

Ben Whitmore in the Cube Forum, 5x5 sliding puzzle can be solved in 205 moves, with updates by Johan de Ruiter claiming 182 moves.

Prog

(Fortran) ! See link in A089473.
(C) /* See Clausecker link. */
(Python) # alst(), moves(), swap() in A089473
start, shape = "-123456789ABCDEFGHIJKLMNO", (5, 5)
alst(start, shape, v=True) # Michael S. Branicky, Dec 31 2020

Crossrefs

Cf. A087725, A088020, A089473, A089484, A090032.

Sequence in context: A247395 A183947 A154322 * A055775 A239076 A217988

Adjacent sequences: A090028 A090029 A090030 * A090032 A090033 A090034

Keyword

fini,hard,nonn

Author

Hugo Pfoertner, Nov 25 2003

Extensions

More terms from Tomas Rokicki, Aug 09 2011

a(28)-a(30) from Robert Clausecker, Jan 29 2018

a(31)-a(32) from Robert Clausecker, Sep 14 2020

Status

approved