A090164 -id:A090164 - 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

A090165 Number of configurations of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square at one of the 8 non-corner boundary squares.

Original entry on oeis.org

1, 3, 6, 14, 32, 66, 134, 280, 585, 1214, 2462, 4946, 9861, 19600, 38688, 76086, 148435, 288098, 554970, 1062628, 2016814, 3800682, 7093209, 13127364, 24053454, 43657576, 78382622, 139237375

Offset: 0

Hugo Pfoertner, Nov 27 2003

Cf. A087725, A089473, A089484, A090164, A090378.

# uses alst(), swap() in A089473
start, shape = "1-23456789ABCDEF", (4, 4)
print(alst(start, shape, maxd=16)) # Michael S. Branicky, Jan 02 2021

a(17)-a(27) 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