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.

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

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

Table of n, a(n) for n=0..31.

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

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.

Sequence in context: A067945 A309263 A166156 * A118021 A326312 A134162

Adjacent sequences: A089470 A089471 A089472 * A089474 A089475 A089476

Keyword

fini,full,nonn

Author

Hugo Pfoertner, Nov 19 2003

Status

approved