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