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

A087725 Maximal number of moves required for the n X n generalization of the sliding block 15-puzzle (or fifteen-puzzle).

Original entry on oeis.org

0, 6, 31, 80

Offset: 1

Jud McCranie, Sep 30 2003

The 15-block puzzle is often referred to (incorrectly) as Sam Loyd's 15-Puzzle (see Slocum and Sonneveld). The actual inventor was Noyes Chapman, the postmaster of Canastota, New York, who applied for a patent in March 1880.
From Dan Hoey, Nov 10 2003: (Start)
The set of moves from a given position depend on where the blank is. There is also a variant in which sliding a row of tiles counts as a single move. For the 8-puzzle I find:
   Move    Blank   Maximum    Number of maximal-distance positions and
   slide   home    distance   (position of blank in those positions)
   tile    corner  31           2 (adjacent edge)
   tile    edge    31           2 (adjacent corner)
   tile    center  30         148 (88 corner, 60 center)
   row     corner  24           1 (center)
   row     edge    24           2 (diagonally adjacent edge)
   row     center  24           4 (corner)
(End)
The maximum number of moves required to solve the 2 X 3 puzzle is 21. The only (solvable) configuration that takes 21 moves to solve is (45*)/(123). - Sergio Pimentel, Jan 29 2008. (See A151943. - N. J. A. Sloane, Aug 16 2009)
For additional comments about the history of the m X n puzzle see the link by Anton Kulchitsky. - N. J. A. Sloane, Aug 16 2009
a(5) >= 114 from Korf and Taylor.
152 <= a(5) <= 208, see links from Hannanov Bulat and Tomas Rokicki, Oct 07 2015
a(5) <= 205, a(6) <= 405, a(7) <= 716, a(8) <= 1164, a(9) <= 1780, a(10) <= 2587. - Ben Whitmore, Jan 18 2018

			All solvable configurations of the Eight Puzzle on a 3 X 3 matrix can be solved in 31 moves or fewer and some configurations require 31 moves, so a(3)=31.

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, see Vol. 2 for the classical 4 X 4 puzzle.
J. C. Culberson and J. Schaeffer, Computer Intelligence, vol. 14.3 (1998) 318-334.
Richard E. Korf and Larry A Taylor, Disjoint pattern database heuristics, in "Chips Challenging Champions" by Schaeffer and Herik, pp. 13-26.
K. Krawiec, Medial Crossovers for Genetic Programming, in Genetic Programming, Springer, 2012.
C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 262.
J. Slocum and D. Sonneveld, The 15 Puzzle, The Slocum Puzzle Foundation, 2006.

A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research 90 (1999), pp. 45-63.
Hannanov Bulat, 208s for 5x5.
Joseph C. Culberson and Jonathan Schaeffer, Searching with Pattern Databases
E. D. Demaine, Playing Games with Algorithms: Algorithmic Combinatorial Game Theory, 2001.
Filip R. W. Karlemo and Patric R. J. Östergård, On Sliding Block Puzzles, J. Combin. Math. Combin. Comp. 34 (2000), 97-107.
Richard E. Korf, Depth-First Iterative-Deeping: An Optimal Admissible Tree Search, Artificial Intelligence, 27(1), 97-110, 1985.
Richard E. Korf and Larry A Taylor, Finding Optimal Solutions to the Twenty-Four Puzzle, Proceedings of the 11th National Conference on Artificial Intelligence, 756-761, 1993.
Anton Kulchitsky, Comments on the Fifteen Puzzle
Swathy Muralidharan, The Fifteen Puzzle--A New Approach, Mathematics Magazine, Vol. 90, No. 1 (February 2017), pp. 48-57.
Ian Parberry, A real-time algorithm for the (n^2 - 1)-puzzle, Inf. Process. Lett. 56 (1995), pp. 23-28.
D. Ratner and M. Warmuth, Finding a shortest solution for the (N x N)-extension of the 15-puzzle is intractable, J. Symbolic Computation, 10: 111-137, 1990.
A. Reinefeld, Complete Solution of the Eight-Puzzle ..., Internat. Joint Conf. Artificial Intell., pp. 248-253, 1993.
Tomas Rokicki, 24 puzzle new lower bound: 152
Eric Weisstein's World of Mathematics, 15 Puzzle in MathWorld
Ben Whitmore, 5x5 sliding puzzle can be solved in 205 moves
Wikipedia, 15 puzzle

Cf. A046164, A090031, A151943.

# alst(), moves(), swap() in A089473
for n in range(1, 4): # chr(45) is "-"
  start, shape = "".join(chr(45+i) for i in range(n**2)), (n, n)
  print(len(alst(start, shape))-1, end=", ") # Michael S. Branicky, Aug 02 2021

Parberry shows that a(n) ≍ n^3, that is, n^3 << a(n) << n^3. In particular, lim inf a(n)/n^3 >= 1 and lim sup a(n)/n^3 <= 5. - Charles R Greathouse IV, Aug 23 2012

Conjecture: a(n) ~ (4/3)*n^3. - Ben Whitmore, May 29 2021

Edited by N. J. A. Sloane, Nov 11 2003
a(3) is from Reinefeld, who used the method of Korf.
a(4) was found by Brüngger, Marzetta, Fukuda and Nievergelt (thanks to Patric Östergård for this reference)

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

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

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

A090377 Number of configurations that require a minimum of n moves to be reached, starting with the empty square in one of the corners of an infinitely large extension of Sam Loyd's sliding block 15-puzzle.

Original entry on oeis.org

1, 2, 4, 10, 26, 66, 173, 456, 1230, 3318, 9066, 24768, 68304, 188370, 523083, 1452560, 4054708, 11318926

Offset: 0

Hugo Pfoertner, Nov 27 2003

The first n terms of this sequence coincide with the first n terms of the corresponding sequences for n X n sliding block puzzles (see Cross-references).

Cf. A089473 (3 X 3 puzzle), A089484 (4 X 4), A090031 (5 X 5), A090032 (6 X 6).

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

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

A264040 Number of possible permutations of the n X n generalization of the sliding block 15-puzzle.

Original entry on oeis.org

1, 12, 181440, 10461394944000, 7755605021665492992000000, 185996663394950608733999724075417600000000, 304140932017133780436126081660647688443776415689605120000000000, 63443466092942082051716694667580740401432758087272596099400947187607352115200000000000000

Offset: 1

Ben Whitmore, Nov 01 2015

For n > 1, of the permutations that can be reached by disassembling the puzzle and replacing the tiles, exactly half of them can be reached by sliding the tiles.

			a(4) = 10461394944000 because the standard 4 X 4 version of the 15-puzzle has exactly 10461394944000 permutations that can be reached by sliding the tiles.

Eric Weisstein's World of Mathematics, 15 Puzzle

Cf. A087725, A090031, A088020.

Mathematica
```
a[n_] := If[n == 1, 1, (n^2)!/2]
```

a(1) = 1; a(n) = (n^2)!/2 for n > 1.

a(1) added by Franklin T. Adams-Watters, Nov 11 2015

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

A087725 Maximal number of moves required for the n X n generalization of the sliding block 15-puzzle (or fifteen-puzzle).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Formula

Extensions

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

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

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

A090377 Number of configurations that require a minimum of n moves to be reached, starting with the empty square in one of the corners of an infinitely large extension of Sam Loyd's sliding block 15-puzzle.

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

Extensions

A264040 Number of possible permutations of the n X n generalization of the sliding block 15-puzzle.

Views

Author