login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A087725 Maximal number of moves required for the n X n generalization of the sliding block 15-puzzle (or fifteen-puzzle). 18
0, 6, 31, 80 (list; graph; refs; listen; history; text; internal format)
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.

Comment from Dan Hoey (Nov 10 2003): 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)

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

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, Depth-First Iterative-Deeping: An Optimal Admissible Tree Search, Artificial Intelligence, 27(1), 97-110, 1985.

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. - From N. J. A. Sloane, Sep 21 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

Table of n, a(n) for n=1..4.

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.

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. Ostergard, On Sliding Block Puzzles, J. Combin. Math. Combin. Comp. 34 (2000), 97-107.

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

Ian Parberry, A real-time algorithm for the (n^2 - 1)-puzzle, Inf. Process. Lett. 56 (1995), pp. 23-28. doi:10.1.1.97.4440

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

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.

CROSSREFS

Cf. A151943, A046164.

Sequence in context: A042841 A215730 A187508 * A096959 A112562 A244716

Adjacent sequences:  A087722 A087723 A087724 * A087726 A087727 A087728

KEYWORD

hard,nonn,nice

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\"ungger, Marzetta, Fukuda and Nievergelt (thanks to Patric Ostergard for this reference)

a(5) >= 114 from Korf and Taylor.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 2 00:27 EDT 2014. Contains 245137 sequences.