A089484 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

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.

REFERENCES

See A087725.

LINKS

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.

PROG

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

start, shape = "-123456789ABCDEF", (4, 4)

alst(start, shape, v=True) # Michael S. Branicky, Dec 31 2020

CROSSREFS