login
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.
9

%I #44 Nov 03 2023 11:17:57

%S 1,2,4,10,26,64,159,366,862,1904,4538,10238,24098,53186,123435,268416,

%T 616374,1326882,3021126,6438828,14524718,30633586,68513713,143106496,

%U 317305688,656178756,1442068376,2951523620,6427133737,13014920506,28070588413,56212979470,120030667717

%N 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.

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

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

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

%D See A087725 for references.

%H Robert Clausecker, <a href="/A090031/a090031.c.txt">term generator puzzledist.c</a>

%H Robert Clausecker, <a href="http://nbn-resolving.de/urn:nbn:de:0297-zib-78489">The Quality of Heuristic Functions for IDA*</a>, Zuse Institute Berlin (2020).

%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/sbpnxn.txt">Configuration counts for n*n sliding block puzzles.</a>

%H Tomas Rokicki, comment in <a href="http://forum.cubeman.org/?q=node/view/238">Twenty-Four puzzle, some observations</a>

%H Ben Whitmore in the Cube Forum, <a href="http://forum.cubeman.org/?q=node/view/559">5x5 sliding puzzle can be solved in 205 moves</a>, with updates by Johan de Ruiter claiming 182 moves.

%o (Fortran) See link in A089473.

%o (C) See Clausecker link.

%o (Python) # alst(), moves(), swap() in A089473

%o start, shape = "-123456789ABCDEFGHIJKLMNO", (5, 5)

%o alst(start, shape, v=True) # _Michael S. Branicky_, Dec 31 2020

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

%K fini,hard,nonn

%O 0,2

%A _Hugo Pfoertner_, Nov 25 2003

%E More terms from _Tomas Rokicki_, Aug 09 2011

%E a(28)-a(30) from _Robert Clausecker_, Jan 29 2018

%E a(31)-a(32) from _Robert Clausecker_, Sep 14 2020