VOOZH about

URL: https://oeis.org/A087725

⇱ A087725 - OEIS

login
A087725
Maximal number of moves required for the n X n generalization of the sliding block 15-puzzle (or fifteen-puzzle).
19
OFFSET
1,2
COMMENTS
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
REFERENCES
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.
LINKS
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
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.
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.
Eric Weisstein's World of Mathematics, 15 Puzzle in MathWorld
Wikipedia, 15 puzzle
FORMULA
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
EXAMPLE
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.
PROG
(Python) # 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
CROSSREFS
KEYWORD
nonn,nice,hard,more
AUTHOR
Jud McCranie, Sep 30 2003
EXTENSIONS
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)
STATUS
approved