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.

%I A089484 #26 Aug 02 2024 14:11:49
%S A089484 1,2,4,10,24,54,107,212,446,946,1948,3938,7808,15544,30821,60842,
%T A089484 119000,231844,447342,859744,1637383,3098270,5802411,10783780,
%U A089484 19826318,36142146,65135623,116238056,204900019,357071928,613926161,1042022040
%N 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.
%C A089484 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.
%C A089484 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.
%D A089484 See A087725.
%H A089484 Herman Jamke, <a href="/A089484/b089484.txt">Table of n, a(n) for n = 0..80</a> (complete sequence)
%H A089484 Herbert Kociemba, <a href="http://kociemba.org/fifteen/fifteensolver.html">15-Puzzle Optimal Solver</a>
%H A089484 R. E. Korf and P. Schultze, <a href="https://www.aaai.org/Library/AAAI/2005/aaai05-219.php">Large-Scale Parallel Breadth-First Search</a>
%H A089484 Hugo Pfoertner, <a href="https://www.randomwalk.de/sequences/sbpnxn.txt">Configuration counts for n*n sliding block puzzles.</a>
%o A089484 (Python) # alst(), moves(), swap() in A089473
%o A089484 start, shape = "-123456789ABCDEF", (4, 4)
%o A089484 alst(start, shape, v=True) # _Michael S. Branicky_, Dec 31 2020
%Y A089484 Cf. A087725, A089473, A090031, A090032, A090164, A090165, A088020.
%K A089484 fini,full,nonn
%O A089484 0,2
%A A089484 _Hugo Pfoertner_, Nov 25 2003
%E A089484 More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Oct 19 2006
%E A089484 Name edited by _Ben Whitmore_, Aug 02 2024