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

Author

Hugo Pfoertner, Nov 25 2003

Keywords

• fini
• hard
• nonn

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

• 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.

Crossrefs

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

Programs

C

/* See Clausecker link. */

Fortran

! See link in A089473.

Python

# alst(), moves(), swap() in A089473
start, shape = "-123456789ABCDEFGHIJKLMNO", (5, 5)
alst(start, shape, v=True) # Michael S. Branicky, Dec 31 2020

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