A089473 -id:A089473 - cp's OEIS frontend

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

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

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

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

A090573 Number of configurations of the 3-dimensional 3 X 3 X 3 sliding cube puzzle that require a minimum of n moves to be reached, starting with the empty space at one of the enclosing cube corners.

Original entry on oeis.org

1, 3, 9, 30, 102, 324, 1029, 3096, 9960, 30732, 97932, 295924, 929202, 2766958, 8590731, 25271897, 77575820

Offset: 0

Hugo Pfoertner, Jan 15 2004

The 3 X 3 X 3 sliding cube puzzle is a generalization of the 2 X 2 X 2 3-D puzzle A090572. There are various designs of this 3 X 3 X 3 puzzle, but in most of them the central cube is not freely accessible and the empty space cannot be moved to the central location of the cube. The design treated in this sequence assumes full accessibility of the central location.

Ji-Ha You, Three dimensional puzzle with blocks - has cube frame with hollow interior and movable blocks filled on one side with magnet. German Patent application DE-4106826 A1, March 4, 1991 - see link

Ji-Ha You, Dreidimensionales Spielgeraet. Offenlegungsschrift DE-4106826 A1.

Cf. A090572 2 X 2 X 2 puzzle, A090574, A090575, A090576 3 X 3 X 3 puzzle with different initial configurations.

# uses alst(), swap() in A089473
def moves3d(p, shape, fixed=None): # n x m x r puzzle
  nxt, (n, m, r) = [], shape
  L, z = n*m, p.find("-") # z: location of blank
  zq, zr = divmod(z, L)
  if zr > n - 1:  nxt.append(swap(p, z, z-n)) # blank up
  if zr < n*m-n:  nxt.append(swap(p, z, z+n)) # blank down
  if zr%n != 0:   nxt.append(swap(p, z, z-1)) # blank left
  if zr%n != n-1: nxt.append(swap(p, z, z+1)) # blank right
  if zq > 0:      nxt.append(swap(p, z, z-L)) # blank in
  if zq < r - 1:  nxt.append(swap(p, z, z+L)) # blank out
  return [m for m in nxt if m.find("-") != fixed]
moves = lambda p, shape: moves3d(p, shape)
start, shape = "-123456789ABCDEFGHIJKLMNOPQ", (3, 3, 3)
print(alst(start, shape, maxd=12)) # Michael S. Branicky, Dec 28 2020

a(13)-a(16) from Michael S. Branicky, Dec 28 2020

cp's OEIS Frontend

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

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