This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A087725 #111 Aug 25 2025 02:12:11 %S A087725 0,6,31,80 %N A087725 Maximal number of moves required for the n X n generalization of the sliding block 15-puzzle (or fifteen-puzzle). %C A087725 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. %C A087725 From _Dan Hoey_, Nov 10 2003: (Start) %C A087725 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: %C A087725 Move Blank Maximum Number of maximal-distance positions and %C A087725 slide home distance (position of blank in those positions) %C A087725 tile corner 31 2 (adjacent edge) %C A087725 tile edge 31 2 (adjacent corner) %C A087725 tile center 30 148 (88 corner, 60 center) %C A087725 row corner 24 1 (center) %C A087725 row edge 24 2 (diagonally adjacent edge) %C A087725 row center 24 4 (corner) %C A087725 (End) %C A087725 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) %C A087725 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 %C A087725 a(5) >= 114 from Korf and Taylor. %C A087725 152 <= a(5) <= 208, see links from Hannanov Bulat and _Tomas Rokicki_, Oct 07 2015 %C A087725 a(5) <= 205, a(6) <= 405, a(7) <= 716, a(8) <= 1164, a(9) <= 1780, a(10) <= 2587. - _Ben Whitmore_, Jan 18 2018 %D A087725 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. %D A087725 J. C. Culberson and J. Schaeffer, Computer Intelligence, vol. 14.3 (1998) 318-334. %D A087725 Richard E. Korf and Larry A Taylor, Disjoint pattern database heuristics, in "Chips Challenging Champions" by Schaeffer and Herik, pp. 13-26. %D A087725 K. Krawiec, Medial Crossovers for Genetic Programming, in Genetic Programming, Springer, 2012. %D A087725 C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 262. %D A087725 J. Slocum and D. Sonneveld, The 15 Puzzle, The Slocum Puzzle Foundation, 2006. %H A087725 A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, <a href="http://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf">The parallel search bench ZRAM and its applications</a>, Annals of Operations Research 90 (1999), pp. 45-63. %H A087725 Hannanov Bulat, <a href="http://forum.cubeman.org/?q=node/view/241/2566#comment-2566">208s for 5x5</a>. %H A087725 Joseph C. Culberson and Jonathan Schaeffer, <a href="http://www.cs.ualberta.ca/~joe/Abstracts/15puzzle.html">Searching with Pattern Databases</a> %H A087725 E. D. Demaine, <a href="http://erikdemaine.org/papers/">Playing Games with Algorithms: Algorithmic Combinatorial Game Theory</a>, 2001. %H A087725 Filip R. W. Karlemo and Patric R. J. Östergård, <a href="http://citeseer.ist.psu.edu/32578.html">On Sliding Block Puzzles</a>, J. Combin. Math. Combin. Comp. 34 (2000), 97-107. %H A087725 Richard E. Korf, <a href="https://doi.org/10.1016/0004-3702(85)90084-0">Depth-First Iterative-Deeping: An Optimal Admissible Tree Search</a>, Artificial Intelligence, 27(1), 97-110, 1985. %H A087725 Richard E. Korf and Larry A Taylor, <a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.6201">Finding Optimal Solutions to the Twenty-Four Puzzle</a>, Proceedings of the 11th National Conference on Artificial Intelligence, 756-761, 1993. %H A087725 Anton Kulchitsky, <a href="/A087725/a087725.txt">Comments on the Fifteen Puzzle</a> %H A087725 Swathy Muralidharan, <a href="https://dx.doi.org/10.4169/math.mag.90.1.48">The Fifteen Puzzle--A New Approach</a>, Mathematics Magazine, Vol. 90, No. 1 (February 2017), pp. 48-57. %H A087725 Ian Parberry, <a href="https://cdn.cs50.net/2010/fall/psets/3/saml.pdf">A real-time algorithm for the (n^2 - 1)-puzzle</a>, Inf. Process. Lett. 56 (1995), pp. 23-28. %H A087725 D. Ratner and M. Warmuth, <a href="http://www.aaai.org/Papers/AAAI/1986/AAAI86-027.pdf">Finding a shortest solution for the (N x N)-extension of the 15-puzzle is intractable</a>, J. Symbolic Computation, 10: 111-137, 1990. %H A087725 A. Reinefeld, <a href="http://www.zib.de/reinefeld/bib/93ijcai.pdf">Complete Solution of the Eight-Puzzle ...</a>, Internat. Joint Conf. Artificial Intell., pp. 248-253, 1993. %H A087725 Tomas Rokicki, <a href="http://forum.cubeman.org/?q=node/view/238#comment-2557">24 puzzle new lower bound: 152</a> %H A087725 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/15Puzzle.html">15 Puzzle in MathWorld</a> %H A087725 Ben Whitmore, <a href="http://forum.cubeman.org/?q=node/view/559">5x5 sliding puzzle can be solved in 205 moves</a> %H A087725 Wikipedia, <a href="http://en.wikipedia.org/wiki/15_puzzle">15 puzzle</a> %F A087725 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 %F A087725 Conjecture: a(n) ~ (4/3)*n^3. - _Ben Whitmore_, May 29 2021 %e A087725 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. %o A087725 (Python) # alst(), moves(), swap() in A089473 %o A087725 for n in range(1, 4): # chr(45) is "-" %o A087725 start, shape = "".join(chr(45+i) for i in range(n**2)), (n, n) %o A087725 print(len(alst(start, shape))-1, end=", ") # _Michael S. Branicky_, Aug 02 2021 %Y A087725 Cf. A046164, A090031, A151943. %K A087725 nonn,nice,hard,more,changed %O A087725 1,2 %A A087725 _Jud McCranie_, Sep 30 2003 %E A087725 Edited by _N. J. A. Sloane_, Nov 11 2003 %E A087725 a(3) is from Reinefeld, who used the method of Korf. %E A087725 a(4) was found by Brüngger, Marzetta, Fukuda and Nievergelt (thanks to Patric Östergård for this reference)