A089483 -id:A089483 - 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.

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

Hugo Pfoertner, Nov 19 2003

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).

			From the starting configuration
123
456
78-
the two final configurations requiring 31 moves are
647 ... 867
85- and 254
321 ... 3-1

For references and links see A087725.

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).

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.

# 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

A089474 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 the center.

Original entry on oeis.org

1, 4, 8, 8, 16, 32, 60, 72, 136, 200, 376, 512, 964, 1296, 2368, 3084, 5482, 6736, 11132, 12208, 18612, 18444, 24968, 19632, 22289, 13600, 11842, 4340, 2398, 472, 148

Offset: 0

Hugo Pfoertner, Nov 19 2003

			Starting with
123
4-5
678
two of the 148 configurations that require the maximum of 30 moves are
476 ... -86
2-8 and 724
351 ... 351

See A087725.

Hugo Pfoertner, Table of solution lengths of the 8-puzzle

Cf. A089473, A089483, A089484, A087725, A090031.

Maple
```
See link in A089473.
```

# alst(), moves(), swap() in A089473
print(alst("1234-5678", (3, 3))) # Michael S. Branicky, Dec 30 2020

A090378 Number of configurations that require a minimum of n moves to be reached, starting with the empty square at mid-side of a boundary of an infinitely large extension of Sam Loyd's sliding block 15-puzzle.

Original entry on oeis.org

1, 3, 7, 19, 53, 147, 409, 1151, 3255, 9241, 26267, 74895, 213775, 611463, 1750277, 5017901

Offset: 0

Hugo Pfoertner, Nov 27 2003

Next term (unconfirmed): a(6)=409. If started with the empty square at mid-side of a boundary, the number of configurations reachable in the first floor((n-1)/2) moves in an n X n sliding block puzzle are given by this sequence.

Cf. A089483 (3 X 3 puzzle started with empty square at mid-side), A090165.

# uses alst(), swap() in A089473
nn = 24
mid = (nn-1)//2
startlst = [chr(i) for i in range(45, 45+nn**2)] # chr(45) is "-"
startlst[0], startlst[mid] = startlst[mid], startlst[0]
start = "".join(startlst)
print(alst(start, (nn, nn), maxd=mid)) # Michael S. Branicky, Jan 02 2021

a(6) confirmed and a(7)-a(15) from Michael S. Branicky, Dec 28 2020

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

A089474 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 the center.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Python

A090378 Number of configurations that require a minimum of n moves to be reached, starting with the empty square at mid-side of a boundary of an infinitely large extension of Sam Loyd's sliding block 15-puzzle.

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

Extensions