|
|
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.
|
|
30
|
|
|
1, 2, 4, 8, 16, 20, 39, 62, 116, 152, 286, 396, 748, 1024, 1893, 2512, 4485, 5638, 9529, 10878, 16993, 17110, 23952, 20224, 24047, 15578, 14560, 6274, 3910, 760, 221, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
J. Knuuttila, S. Broman and P. Ranta, n-Puzzle, in Finnish (2002).
|
|
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
|
|
CROSSREFS
|
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.
|
|
KEYWORD
|
fini,full,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|