|
%I #14 Dec 29 2020 06:31:54
%S 1,2,4,8,16,20,39,62,116,152,286,396,748,1024,1893,2512,4485,5638,
%T 9529,10878,16993,17110,23952,20224,24047,15578,14560,6274,3910,760,
%U 221,2
%N 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 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 For references and links see A087725.
%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/a089473.txt">FORTRAN program to solve small sliding block puzzles.</a>
%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/sbpuzz33.txt">Table of solution lengths of the 8-puzzle</a>
%H I. Kapustik, <a href="http://www2.fiit.stuba.sk/~kapustik/cesta%203x3.html">Cesta</a>.
%H J. Knuuttila, S. Broman and P. Ranta, <a href="http://14142.net/n-puzzle/document/document.html">n-Puzzle</a>, in Finnish (2002).
%H 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 Takaken, <a href="http://www.ic-net.or.jp/home/takaken/nt/slide/index.html">n-Puzzle Page</a>.
%H Takaken, <a href="http://www.ic-net.or.jp/home/takaken/nt/slide/result33.txt">No. 33 (8 puzzles)</a>.
%e From the starting configuration
%e 123
%e 456
%e 78-
%e the two final configurations requiring 31 moves are
%e 647 ... 867
%e 85- and 254
%e 321 ... 3-1
%o See link.
%o (Python) # alst(), swap(), moves() useful for other sliding puzzle problems
%o def swap(p, z, nz):
%o lp = list(p)
%o lp[z], lp[nz] = lp[nz], "-"
%o return "".join(lp)
%o def moves(p, shape): # moves for n x m sliding puzzle
%o nxt, (n, m), z = [], shape, p.find("-") # z: blank location
%o if z > n - 1: nxt.append(swap(p, z, z-n)) # blank up
%o if z < n*m-n: nxt.append(swap(p, z, z+n)) # blank down
%o if z%n != 0: nxt.append(swap(p, z, z-1)) # blank left
%o if z%n != n-1: nxt.append(swap(p, z, z+1)) # blank right
%o return nxt
%o def alst(start, shape, v=False, maxd=float('inf')):
%o alst, d, expanded, frontier = [], 0, set(), {start}
%o alst.append(len(frontier))
%o if v: print(len(frontier), end=", ")
%o while len(frontier) > 0 and d < maxd:
%o reach1 = set(m for p in frontier for m in moves(p, shape) if m not in expanded)
%o expanded |= frontier # expanded = frontier # ALTERNATE using less memory
%o if len(reach1):
%o alst.append(len(reach1))
%o if v: print(len(reach1), end=", ")
%o frontier = reach1
%o d += 1
%o return alst
%o print(alst("-12345678", (3, 3))) # _Michael S. Branicky_, Dec 28 2020
%Y 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 fini,full,nonn
%O 0,2
%A _Hugo Pfoertner_, Nov 19 2003
|
