cp's OEIS Frontend

A089473 Number of configurations of the sliding block 8-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

%I A089473 #14 Dec 29 2020 06:31:54
%S A089473 1,2,4,8,16,20,39,62,116,152,286,396,748,1024,1893,2512,4485,5638,
%T A089473 9529,10878,16993,17110,23952,20224,24047,15578,14560,6274,3910,760,
%U A089473 221,2
%N A089473 Number of configurations of the sliding block 8-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.
%C A089473 The sequence was first provided by Alexander Reinefeld in Table 1 of "Complete Solution of the Eight-Puzzle..." (see corresponding link in A087725) with a typo "749" instead of "748" for a(12).
%D A089473 For references and links see A087725.
%H A089473 Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/a089473.txt">FORTRAN program to solve small sliding block puzzles.</a>
%H A089473 Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/sbpuzz33.txt">Table of solution lengths of the 8-puzzle</a>
%H A089473 I. Kapustik, <a href="http://www2.fiit.stuba.sk/~kapustik/cesta%203x3.html">Cesta</a>.
%H A089473 J. Knuuttila, S. Broman and P. Ranta, <a href="http://14142.net/n-puzzle/document/document.html">n-Puzzle</a>, in Finnish (2002).
%H A089473 A. Reinefeld, <a href="http://web.archive.org/web/20070630064952/http://www.zib.de/reinefeld/bib/93ijcai.pdf">Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*</a>. Proc. 13th Int. Joint Conf. on Artificial Intelligence (1993), Chambery Savoi, France, pp. 248-253.
%H A089473 Takaken, <a href="http://www.ic-net.or.jp/home/takaken/nt/slide/index.html">n-Puzzle Page</a>.
%H A089473 Takaken, <a href="http://www.ic-net.or.jp/home/takaken/nt/slide/result33.txt">No. 33 (8 puzzles)</a>.
%e A089473 From the starting configuration
%e A089473 123
%e A089473 456
%e A089473 78-
%e A089473 the two final configurations requiring 31 moves are
%e A089473 647 ... 867
%e A089473 85- and 254
%e A089473 321 ... 3-1
%o A089473 See link.
%o A089473 (Python) # alst(), swap(), moves() useful for other sliding puzzle problems
%o A089473 def swap(p, z, nz):
%o A089473   lp = list(p)
%o A089473   lp[z], lp[nz] = lp[nz], "-"
%o A089473   return "".join(lp)
%o A089473 def moves(p, shape): # moves for n x m sliding puzzle
%o A089473   nxt, (n, m), z = [], shape, p.find("-") # z: blank location
%o A089473   if z > n - 1:  nxt.append(swap(p, z, z-n)) # blank up
%o A089473   if z < n*m-n:  nxt.append(swap(p, z, z+n)) # blank down
%o A089473   if z%n != 0:   nxt.append(swap(p, z, z-1)) # blank left
%o A089473   if z%n != n-1: nxt.append(swap(p, z, z+1)) # blank right
%o A089473   return nxt
%o A089473 def alst(start, shape, v=False, maxd=float('inf')):
%o A089473   alst, d, expanded, frontier = [], 0, set(), {start}
%o A089473   alst.append(len(frontier))
%o A089473   if v: print(len(frontier), end=", ")
%o A089473   while len(frontier) > 0 and d < maxd:
%o A089473     reach1 = set(m for p in frontier for m in moves(p, shape) if m not in expanded)
%o A089473     expanded |= frontier # expanded = frontier # ALTERNATE using less memory
%o A089473     if len(reach1):
%o A089473       alst.append(len(reach1))
%o A089473       if v: print(len(reach1), end=", ")
%o A089473     frontier = reach1
%o A089473     d += 1
%o A089473   return alst
%o A089473 print(alst("-12345678", (3, 3))) # _Michael S. Branicky_, Dec 28 2020
%Y A089473 Cf. A087725 = maximum number of moves for n X n puzzle, A089474 = 8-puzzle starting with blank square at center, A089483 = 8-puzzle starting with blank square at mid-side, A089484 = solution lengths for 15-puzzle, A090031 - A090036 = other sliding block puzzles.
%K A089473 fini,full,nonn
%O A089473 0,2
%A A089473 _Hugo Pfoertner_, Nov 19 2003