|
%I #106 Aug 02 2021 06:39:57
%S 0,6,31,80
%N Maximal number of moves required for the n X n generalization of the sliding block 15-puzzle (or fifteen-puzzle).
%C 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 From _Dan Hoey_, Nov 10 2003: (Start)
%C 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 Move Blank Maximum Number of maximal-distance positions and
%C slide home distance (position of blank in those positions)
%C tile corner 31 2 (adjacent edge)
%C tile edge 31 2 (adjacent corner)
%C tile center 30 148 (88 corner, 60 center)
%C row corner 24 1 (center)
%C row edge 24 2 (diagonally adjacent edge)
%C row center 24 4 (corner)
%C (End)
%C 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 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 a(5) >= 114 from Korf and Taylor.
%C 152 <= a(5) <= 208, see links from Hannanov Bulat and Tomas Rokicki, Oct 07 2015
%C a(5) <= 205, a(6) <= 405, a(7) <= 716, a(8) <= 1164, a(9) <= 1780, a(10) <= 2587. - _Ben Whitmore_, Jan 18 2018
%D 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 J. C. Culberson and J. Schaeffer, Computer Intelligence, vol. 14.3 (1998) 318-334.
%D Richard E. Korf and Larry A Taylor, Disjoint pattern database heuristics, in "Chips Challenging Champions" by Schaeffer and Herik, pp. 13-26.
%D K. Krawiec, Medial Crossovers for Genetic Programming, in Genetic Programming, Springer, 2012.
%D C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 262.
%D J. Slocum and D. Sonneveld, The 15 Puzzle, The Slocum Puzzle Foundation, 2006.
%H 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 Hannanov Bulat, <a href="http://forum.cubeman.org/?q=node/view/241/2566#comment-2566">208s for 5x5</a>.
%H Joseph C. Culberson and Jonathan Schaeffer, <a href="http://www.cs.ualberta.ca/~joe/Abstracts/15puzzle.html">Searching with Pattern Databases</a>
%H E. D. Demaine, <a href="http://erikdemaine.org/papers/">Playing Games with Algorithms: Algorithmic Combinatorial Game Theory</a>, 2001.
%H 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 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 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 Anton Kulchitsky, <a href="/A087725/a087725.txt">Comments on the Fifteen Puzzle</a>
%H 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 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 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 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 Tomas Rokicki, <a href="http://forum.cubeman.org/?q=node/view/238#comment-2557">24 puzzle new lower bound: 152</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/15Puzzle.html">15 Puzzle in MathWorld</a>
%H Ben Whitmore, <a href="http://forum.cubeman.org/?q=node/view/559">5x5 sliding puzzle can be solved in 205 moves</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/15_puzzle">15 puzzle</a>
%F 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 Conjecture: a(n) ~ (4/3)*n^3. - _Ben Whitmore_, May 29 2021
%e 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 (Python) # alst(), moves(), swap() in A089473
%o for n in range(1, 4): # chr(45) is "-"
%o start, shape = "".join(chr(45+i) for i in range(n**2)), (n, n)
%o print(len(alst(start, shape))-1, end=", ") # _Michael S. Branicky_, Aug 02 2021
%Y Cf. A046164, A090031, A151943.
%K nonn,nice,hard,more
%O 1,2
%A _Jud McCranie_, Sep 30 2003
%E Edited by _N. J. A. Sloane_, Nov 11 2003
%E a(3) is from Reinefeld, who used the method of Korf.
%E a(4) was found by Brüngger, Marzetta, Fukuda and Nievergelt (thanks to Patric Östergård for this reference)
| 