A090032 -id:A090032 - cp's OEIS frontend

A089484 Number of positions of the 15-puzzle at a distance of n moves from an initial state with the empty square in one of the corners, in the single-tile metric.

1, 2, 4, 10, 24, 54, 107, 212, 446, 946, 1948, 3938, 7808, 15544, 30821, 60842, 119000, 231844, 447342, 859744, 1637383, 3098270, 5802411, 10783780, 19826318, 36142146, 65135623, 116238056, 204900019, 357071928, 613926161, 1042022040

Offset: 0

Hugo Pfoertner, Nov 25 2003

The single-tile metric counts moves of individual tiles as 1 move. Moving multiple tiles at once counts as more than one move, e.g. simultaneously sliding 3 tiles along a row or column counts as 3 moves.

The last term is a(80). The total number of possible configurations of an m X m sliding block puzzle is (m*m)!/2 = A088020(4)/2, therefore, Sum_i (i=0..80) a(i) = 16!/2 = 10461394944000.

See A087725.

Herman Jamke, Table of n, a(n) for n = 0..80 (complete sequence)
Herbert Kociemba, 15-Puzzle Optimal Solver
R. E. Korf and P. Schultze, Large-Scale Parallel Breadth-First Search
Hugo Pfoertner, Configuration counts for n*n sliding block puzzles.

Cf. A087725, A089473, A090031, A090032, A090164, A090165, A088020.

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

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Oct 19 2006

Name edited by Ben Whitmore, Aug 02 2024

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.

Original entry on oeis.org

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

Hugo Pfoertner, Nov 25 2003

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

See A087725 for references.

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.

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

C
```
/* See Clausecker link. */
```
Fortran
```
! See link in A089473.
```

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

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

A090377 Number of configurations that require a minimum of n moves to be reached, starting with the empty square in one of the corners of an infinitely large extension of Sam Loyd's sliding block 15-puzzle.

Original entry on oeis.org

1, 2, 4, 10, 26, 66, 173, 456, 1230, 3318, 9066, 24768, 68304, 188370, 523083, 1452560, 4054708, 11318926

Offset: 0

Hugo Pfoertner, Nov 27 2003

The first n terms of this sequence coincide with the first n terms of the corresponding sequences for n X n sliding block puzzles (see Cross-references).

Cf. A089473 (3 X 3 puzzle), A089484 (4 X 4), A090031 (5 X 5), A090032 (6 X 6).

# uses alst(), swap() in A089473
nn = 13
start = "".join([chr(i) for i in range(45, 45+(nn+1)**2)]) # chr(45) is "-"
print(alst(start, (nn+1, nn+1), maxd=nn)) # Michael S. Branicky, Jan 02 2021

a(10)-a(17) from Michael S. Branicky, Dec 28 2020

cp's OEIS Frontend

A089484 Number of positions of the 15-puzzle at a distance of n moves from an initial state with the empty square in one of the corners, in the single-tile metric.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Python

Extensions

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

C

Fortran

Python

Extensions

A090377 Number of configurations that require a minimum of n moves to be reached, starting with the empty square in one of the corners of an infinitely large extension of Sam Loyd's sliding block 15-puzzle.

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

Extensions