OFFSET
0,2
COMMENTS
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).
REFERENCES
For references and links see A087725.
LINKS
Hugo Pfoertner, FORTRAN program to solve small sliding block puzzles.
Hugo Pfoertner, Table of solution lengths of the 8-puzzle
I. Kapustik, Cesta.
J. Knuuttila, S. Broman and P. Ranta, n-Puzzle, in Finnish (2002).
A. Reinefeld, Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*. Proc. 13th Int. Joint Conf. on Artificial Intelligence (1993), Chambery Savoi, France, pp. 248-253.
Takaken, n-Puzzle Page.
Takaken, No. 33 (8 puzzles).
EXAMPLE
From the starting configuration
123
456
78-
the two final configurations requiring 31 moves are
647 ... 867
85- and 254
321 ... 3-1
PROG
See link.
(Python) # alst(), swap(), moves() useful for other sliding puzzle problems
def swap(p, z, nz):
lp = list(p)
lp[z], lp[nz] = lp[nz], "-"
return "".join(lp)
def moves(p, shape): # moves for n x m sliding puzzle
nxt, (n, m), z = [], shape, p.find("-") # z: blank location
if z > n - 1: nxt.append(swap(p, z, z-n)) # blank up
if z < n*m-n: nxt.append(swap(p, z, z+n)) # blank down
if z%n != 0: nxt.append(swap(p, z, z-1)) # blank left
if z%n != n-1: nxt.append(swap(p, z, z+1)) # blank right
return nxt
def alst(start, shape, v=False, maxd=float('inf')):
alst, d, expanded, frontier = [], 0, set(), {start}
alst.append(len(frontier))
if v: print(len(frontier), end=", ")
while len(frontier) > 0 and d < maxd:
reach1 = set(m for p in frontier for m in moves(p, shape) if m not in expanded)
expanded |= frontier # expanded = frontier # ALTERNATE using less memory
if len(reach1):
alst.append(len(reach1))
if v: print(len(reach1), end=", ")
frontier = reach1
d += 1
return alst
print(alst("-12345678", (3, 3))) # Michael S. Branicky, Dec 28 2020
CROSSREFS
KEYWORD
fini,full,nonn
AUTHOR
Hugo Pfoertner, Nov 19 2003
STATUS
approved