A089484 -id:A089484 - 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

A090033 Triangle T(j,k) read by rows, where T(j,k) is the number of single tile moves in the longest optimal solution of the j X k generalization of the sliding block 15-puzzle, starting with the empty square in a corner.

Original entry on oeis.org

0, 1, 6, 2, 21, 31, 3, 36, 53, 80, 4, 55, 84

Offset: 1

Hugo Pfoertner, Nov 23 2003

T(k,j) = T(j,k).

T(2,2), T(2,3), T(4,2), T(4,3) from Karlemo and Östergård, T(3,3) from Reinefeld, T(4,4) from Bruengger et al.

			The triangle begins
  0
  1   6
  2  21  31
  3  36  53  80
  4  55  84  ...
.
a(6)=T(3,3)=31 because the A090163(3,3)=2 longest optimal solution paths of the 3 X 3 (9-) sliding block puzzle have length 31 (see A089473).

For references and links see A087725(n)=T(n,n).

Cf. A087725, A089473, A089484, A090034, A090035, A090036, A090166, A090163 corresponding number of different configurations with largest distance.

Cf. A151944 same as this sequence, but written as full array.

# alst(), moves(), swap() in A089473
def T(j, k):  # chr(45) is '-'
    start, shape = "".join(chr(45+i) for i in range(j*k)), (j, k)
    return len(alst(start, shape))-1
for j in range(1, 5):
    for k in range(1, j+1):
        print(T(j,k), end=", ") # Michael S. Branicky, Aug 02 2021

T(5,3) copied from A151944 by Hugo Pfoertner, Aug 02 2021

A090031 Number of configurations of the 5 X 5 variant of sliding block 15-puzzle ("24-puzzle") that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Original entry on oeis.org

1, 2, 4, 10, 26, 64, 159, 366, 862, 1904, 4538, 10238, 24098, 53186, 123435, 268416, 616374, 1326882, 3021126, 6438828, 14524718, 30633586, 68513713, 143106496, 317305688, 656178756, 1442068376, 2951523620, 6427133737, 13014920506, 28070588413, 56212979470, 120030667717

Offset: 0

Hugo Pfoertner, Nov 25 2003

The 15-block puzzle is often referred to (incorrectly) as Sam Loyd's 15-Puzzle.
Sum of sequence terms = A088020(5)/2.
152 <= (number of last sequence term) <= 205 (see A087725 and cube archives link for current status).  - Hugo Pfoertner, Feb 12 2020

See A087725 for references.

Robert Clausecker, term generator puzzledist.c
Robert Clausecker, The Quality of Heuristic Functions for IDA*, Zuse Institute Berlin (2020).
Hugo Pfoertner, Configuration counts for n*n sliding block puzzles.
Tomas Rokicki, comment in Twenty-Four puzzle, some observations
Ben Whitmore in the Cube Forum, 5x5 sliding puzzle can be solved in 205 moves, with updates by Johan de Ruiter claiming 182 moves.

Cf. A087725, A088020, A089473, A089484, A090032.

C
```
/* See Clausecker link. */
```
Fortran
```
! See link in A089473.
```

# alst(), moves(), swap() in A089473
start, shape = "-123456789ABCDEFGHIJKLMNO", (5, 5)
alst(start, shape, v=True) # Michael S. Branicky, Dec 31 2020

More terms from Tomas Rokicki, Aug 09 2011
a(28)-a(30) from Robert Clausecker, Jan 29 2018
a(31)-a(32) from Robert Clausecker, Sep 14 2020

A090572 Number of configurations of the 3-dimensional 2 X 2 X 2 sliding cube puzzle that require a minimum of n moves to be reached.

Original entry on oeis.org

1, 3, 6, 12, 24, 48, 93, 180, 351, 675, 1191, 1963, 3015, 3772, 3732, 2837, 1589, 572, 78, 18

Offset: 0

Hugo Pfoertner, Jan 14 2004

This puzzle is a 3-dimensional generalization of the so-called "Sam Loyd" 15-puzzle. A description is given in the now expired German patent 2152360 (see link).
Same as the number of configurations for the Varikon Box (see Jaapsch link) and others 2 X 2 X 2 sliding cube puzzles. The basic idea for this sliding block puzzle seems to be very old, long before Mr. Lurker's patent (see van der Schagt's article for details): Charles I. Rice patented a 2 X 2 X 2 version with peepholes in the faces in 1889. US Patent 416,344 _ Puzzle. Applied 9 Sep 1889; patented 3 Dec 1889. 2pp + 1p diagrams. Described in L. Edward Hordern. Sliding Piece Puzzles. OUP, 1986, pp. 27 & 157-158, G2. - Herman Jamke (hermanjamke(AT)fastmail.fm), Oct 21 2006
In the late 1970's the Hungarians produced 2 X 2 X 2 versions within transparent cubes: Naef's beautiful 2 X 2 X 2 one, Vadasz 2 X 2 X 2 Cube, ... First one 2 X 2 X 2 sold commercially was designed by Piet Hein around 1972 and named Bloxbox. Martin Gardner described it for first time (Scientific American Feb, 1973, page 109). - Herman Jamke (hermanjamke(AT)fastmail.fm), Oct 21 2006
The puzzle was made and sold in Japan under the name Qrazy Qube by Kawada in 1981. Another version was made and sold in Japan by Maruhaya (2 X 2 X 2) in 1981. The Varikon Box'S 2 X 2 X 2 puzzle of 1982 was invented by Csaba Postasy, Gabor Eszes and Miklos Zagoni. German patent, DE 3,027,556, published on Jun 19 1981. - Herman Jamke (hermanjamke(AT)fastmail.fm), Oct 21 2006

			a(19) = 18 because 18 of the total 20160 possible configurations cannot be reached in fewer than 19 single-cube moves.

Jaap's Puzzle Page: Varikon Box 2 X 2 X 2.
Werner Lurker, Dreidimensionales puzzleaehnliches Spielzeug. German Patent 2152360, filed Oct 21 1971
Hugo Pfoertner, List of the most distant configurations for the 2X2X2 sliding cube puzzle.
Ad van der Schagt, The History of Sliding Block puzzles before Peter's Black Hole.

Cf. A090573 - A090578 configurations of 3 X 3 X 3 sliding cube puzzles, A089484 4 X 4 (15-)puzzle.

# uses alst(), swap() in A089473, moves3d() in A090573
moves = lambda p, shape: moves3d(p, shape)
print(alst("-1234567", (2, 2, 2))) # Michael S. Branicky, Dec 31 2020

A089483 Number of configurations of the sliding block 8-puzzle that require a minimum of n moves to be reached, starting with the empty square at mid-side.

Original entry on oeis.org

1, 3, 5, 10, 14, 28, 42, 80, 108, 202, 278, 524, 726, 1348, 1804, 3283, 4193, 7322, 8596, 13930, 14713, 21721, 19827, 25132, 18197, 18978, 9929, 7359, 2081, 878, 126, 2

Offset: 0

Hugo Pfoertner, Nov 19 2003

			Starting with
1-2
345
678
the two final configurations requiring 31 moves are
86- ... -86
547 and 743
231 ... 251

See A087725.

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

Cf. A089473, A089474, A089484, A087725, A090031.

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

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

A090032 Number of configurations of the 6 X 6 variant of Sam Loyd's sliding block 15-puzzle ("35-puzzle") that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Original entry on oeis.org

1, 2, 4, 10, 26, 66, 171, 440, 1112, 2786, 6820, 16720, 41106, 100856, 245793, 597030, 1441292, 3469486, 8304526, 19832076, 47110238, 111669014

Offset: 0

Hugo Pfoertner, Nov 25 2003

See A087725.

Hugo Pfoertner, Configuration counts for n*n sliding block puzzles.

Cf. A087725, A089473, A089484, A090031.

# uses alst(), swap() in A089473
start, shape = "-123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ", (6, 6)
print(alst(start, shape, maxd=16)) # Michael S. Branicky, Jan 02 2021

a(17)-a(21) from Michael S. Branicky, Dec 28 2020

A090165 Number of configurations of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square at one of the 8 non-corner boundary squares.

Original entry on oeis.org

1, 3, 6, 14, 32, 66, 134, 280, 585, 1214, 2462, 4946, 9861, 19600, 38688, 76086, 148435, 288098, 554970, 1062628, 2016814, 3800682, 7093209, 13127364, 24053454, 43657576, 78382622, 139237375

Offset: 0

Hugo Pfoertner, Nov 27 2003

Cf. A087725, A089473, A089484, A090164, A090378.

# uses alst(), swap() in A089473
start, shape = "1-23456789ABCDEF", (4, 4)
print(alst(start, shape, maxd=16)) # Michael S. Branicky, Jan 02 2021

a(17)-a(27) from Michael S. Branicky, Dec 28 2020

A346736 Number of configurations of the 7 X 2 variant of the sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Original entry on oeis.org

1, 2, 3, 6, 11, 20, 37, 67, 117, 198, 329, 557, 942, 1575, 2597, 4241, 6724, 10535, 16396, 25515, 39362, 60532, 92089, 138969, 207274, 307725, 453000, 664240, 964874, 1392975, 1992353, 2832063, 3988528, 5586275, 7756511, 10698721, 14621717, 19840724, 26676629

Offset: 0

Ben Whitmore, Jul 31 2021

This sequence was originally computed by Richard Korf, but the full sequence was not included in his paper. It was later re-computed by Tomas Rokicki.

			Starting from the solved configuration
  1  2  3  4  5  6  7
  8  9 10 11 12 13
the unique configuration requiring 108 moves is
  7  6 12  4  3  9  1
    13  5 11 10  2  8

Ben Whitmore, Table of n, a(n) for n = 0..108
Richard Korf, Linear-time Disk-Based Implicit Graph Search, Journal of the ACM 55 (2008), No. 6.
Tomas Rokicki, Twenty-Four puzzle, some observations, 2011.

Cf. A090033, A090034, A090035, A090036, A090167, A089473, A089484.

# alst(), moves(), swap() in A089473
print(alst("-123456789abcd", (7, 2), v=True)) # Michael S. Branicky, Jul 31 2021

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

A090164 Number of configurations of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square at one of the 4 central squares.

Original entry on oeis.org

1, 4, 10, 20, 38, 80, 174, 372, 762, 1540, 3072, 6196, 12356, 24516, 48179, 94356, 183432, 355330, 682250, 1301874, 2460591, 4617322, 8580175, 15815664, 28854386, 52154316, 93214030

Offset: 0

Hugo Pfoertner, Nov 27 2003

Cf. A087725, A089484, A090165.

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

# uses alst(), swap() in A089473
start, shape = "12345-6789ABCDEF", (4, 4)
print(alst(start, shape, maxd=15)) # Michael S. Branicky, Jan 02 2021

a(16)-a(26) 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

A090033 Triangle T(j,k) read by rows, where T(j,k) is the number of single tile moves in the longest optimal solution of the j X k generalization of the sliding block 15-puzzle, starting with the empty square in a corner.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Python

Extensions

A090031 Number of configurations of the 5 X 5 variant of sliding block 15-puzzle ("24-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

References

Links

Crossrefs

Programs

C

Fortran

Python

Extensions

A090572 Number of configurations of the 3-dimensional 2 X 2 X 2 sliding cube puzzle that require a minimum of n moves to be reached.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A089483 Number of configurations of the sliding block 8-puzzle that require a minimum of n moves to be reached, starting with the empty square at mid-side.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Python

A090032 Number of configurations of the 6 X 6 variant of Sam Loyd's sliding block 15-puzzle ("35-puzzle") that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

Extensions

A090165 Number of configurations of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square at one of the 8 non-corner boundary squares.

Views

Author

Keywords

Crossrefs

Programs

Python

Extensions

A346736 Number of configurations of the 7 X 2 variant of the sliding block 15-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