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

A089484 Number of positions of the 15-puzzle at a distance of n moves from an initial state with the empty square in one of the corners, in the single-tile metric.

Original entry on oeis.org

1, 2, 4, 10, 24, 54, 107, 212, 446, 946, 1948, 3938, 7808, 15544, 30821, 60842, 119000, 231844, 447342, 859744, 1637383, 3098270, 5802411, 10783780, 19826318, 36142146, 65135623, 116238056, 204900019, 357071928, 613926161, 1042022040

Offset: 0

Hugo Pfoertner, Nov 25 2003

The single-tile metric counts moves of individual tiles as 1 move. Moving multiple tiles at once counts as more than one move, e.g. simultaneously sliding 3 tiles along a row or column counts as 3 moves.

The last term is a(80). The total number of possible configurations of an m X m sliding block puzzle is (m*m)!/2 = A088020(4)/2, therefore, Sum_i (i=0..80) a(i) = 16!/2 = 10461394944000.

See A087725.

Herman Jamke, Table of n, a(n) for n = 0..80 (complete sequence)
Herbert Kociemba, 15-Puzzle Optimal Solver
R. E. Korf and P. Schultze, Large-Scale Parallel Breadth-First Search
Hugo Pfoertner, Configuration counts for n*n sliding block puzzles.

Cf. A087725, A089473, A090031, A090032, A090164, A090165, A088020.

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

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Oct 19 2006

Name edited by Ben Whitmore, Aug 02 2024

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

A090034 Number of configurations of the 3 X 2 variant of Sam Loyd's 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, 5, 6, 7, 10, 12, 12, 16, 23, 25, 28, 39, 44, 40, 29, 21, 18, 12, 6, 1

Offset: 0

Hugo Pfoertner, Nov 23 2003

Data from Karlemo and Östergård. See corresponding link in A087725.

			Starting with
123
45-
the most distant configuration corresponding to a(21)=1 is
45-
123 (i.e., it takes longest just to swap the two rows).

See A087725.

Hugo Pfoertner, Solutions of small n*2 sliding block puzzles.
Takaken, n-Puzzle Page.
Takaken, No. 32 (5 puzzles).

Cf. A087725, A089473, A090033, A090035, A090036, A090163, A090167.

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

A090036 Number of configurations of the 5 X 2 variant of Sam Loyd's 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, 19, 30, 44, 68, 112, 176, 271, 411, 602, 851, 1232, 1783, 2530, 3567, 4996, 6838, 9279, 12463, 16597, 21848, 28227, 35682, 44464, 54597, 65966, 78433, 91725, 104896, 116966, 126335, 131998, 133107, 128720, 119332, 106335, 91545, 75742, 60119, 45840, 33422, 23223, 15140, 9094, 5073, 2605, 1224, 528, 225, 75, 20, 2

Offset: 0

Hugo Pfoertner, Nov 27 2003

			Starting from
12345
6789-
the 2 most distant configurations corresponding to a(55)=2 are
-9371 and -5321
54826.....94876

Hugo Pfoertner, Solutions of small n*2 sliding block puzzles.
Takaken, 11-Puzzle Page.
Takaken, No. 52 (9 puzzles).

Cf. A087725, A089473. Index of last sequence term: A090033. Other nonsquare sliding block puzzles: A090034, A090035, A090166, A090167.

# alst(), moves(), swap() in A089473
print(alst("-123456789", (5, 2))) # Michael S. Branicky, Dec 30 2020

A090035 Number of configurations of the 4 X 2 variant of Sam Loyd's 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, 10, 14, 19, 28, 42, 61, 85, 119, 161, 215, 293, 396, 506, 632, 788, 985, 1194, 1414, 1664, 1884, 1999, 1958, 1770, 1463, 1076, 667, 361, 190, 88, 39, 19, 7, 1

Offset: 0

Hugo Pfoertner, Nov 26 2003

Data from Karlemo, Östergård. See corresponding link in A087725.

			Starting from
1234
567-
the most distant configuration corresponding to a(36)=1 is
-721
4365

See A087725.

Hugo Pfoertner, Solutions of small n*2 sliding block puzzles.
Takaken, n-Puzzle Page.
Takaken, No. 42 (7 puzzles).

Cf. A087725, A089473. Index of last sequence term: A090033. Other nonsquare sliding block puzzles: A090034, A090036, A090166, A090167.

# alst(), moves(), swap() in A089473
print(alst("-1234567", (4, 2))) # Michael S. Branicky, Dec 30 2020

A090167 Number of configurations of the 6 X 2 variant of the so-called "Sam Loyd" 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, 36, 60, 95, 155, 258, 426, 688, 1106, 1723, 2615, 3901, 5885, 8851, 13205, 19508, 28593, 41179, 58899, 83582, 118109, 165136, 228596, 312542, 423797, 568233, 755727, 994641, 1296097, 1667002, 2119476, 2660415, 3300586, 4038877

Offset: 0

Hugo Pfoertner, Nov 27 2003

Herman Jamke, Table of n, a(n) for n = 0..80 (complete sequence)
Hugo Pfoertner, Solutions of small n*2 sliding block puzzles.
Takaken, 11-Puzzle Page.
Takaken, No. 62 (11 puzzles).

Cf. A087725, A089473. Index of last sequence term: A090033. Other nonsquare sliding block puzzles: A090034, A090035, A090036, A090166.

# alst(), moves(), swap() in A089473
alst("-123456789AB", (6, 2), v=True) # Michael S. Branicky, Dec 31 2020

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Oct 22 2006

A090166 Number of configurations of the 4 X 3 variant of Sam Loyd's 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, 4, 9, 20, 37, 63, 122, 232, 431, 781, 1392, 2494, 4442, 7854, 13899, 24215, 41802, 71167, 119888, 198363, 323206, 515778, 811000, 1248011, 1885279, 2782396, 4009722, 5621354, 7647872, 10065800, 12760413, 15570786, 18171606, 20299876, 21587248, 21841159, 20906905, 18899357, 16058335, 12772603, 9515217, 6583181, 4242753, 2503873, 1350268, 643245, 270303, 92311, 27116, 5390, 1115, 86, 18

Offset: 0

Hugo Pfoertner, Nov 27 2003, Jul 07 2007

Data from Karlemo and Östergård.

Filip R. W. Karlemo and Patric R. J. Östergård, On Sliding Block Puzzles, J. Combin. Math. Combin. Comp. 34 (2000), 97-107.
Takaken, 11-Puzzle Page.
Takaken, No. 43 (11 puzzles).

Cf. A087725. Index of last sequence term: A090033. Other nonsquare sliding block puzzles: A090034, A090035, A090036, A090167.

# alst(), moves(), swap() in A089473
alst("-123456789AB", (4, 3), v=True) # 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

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

A089484 Number of positions of the 15-puzzle at a distance of n moves from an initial state with the empty square in one of the corners, in the single-tile metric.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Python

Extensions

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

A090034 Number of configurations of the 3 X 2 variant of Sam Loyd's 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

Examples

References

Links

Crossrefs

Programs

Python

A090036 Number of configurations of the 5 X 2 variant of Sam Loyd's 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

Examples

Links

Crossrefs

Programs

Python

A090035 Number of configurations of the 4 X 2 variant of Sam Loyd's 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

Examples

References

Links

Crossrefs

Programs

Python

A090167 Number of configurations of the 6 X 2 variant of the so-called "Sam Loyd" 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