|
|
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.
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
|
Filip R. W. Karlemo and Patric R. J. Östergård, On Sliding Block Puzzles, J. Combin. Math. Combin. Comp. 34 (2000), 97-107.
|
|
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
|
|
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)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
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
|
|
|
|