A151943 Maximal number of moves required for the 2 X n generalization of the sliding block 15-puzzle (or fifteen-puzzle).

1, 6, 21, 36, 55, 80, 108, 140

Offset

1,2

Comments

See A087725 for more about this problem and its history. See also A151944.

Three corrections to table III of the Korf reference: the radius of the 2 X 4 should be 36; the depth of the 3 X 5 should be 52, and the ratio of the 3 X 5 should be 14.379. - Tomas Rokicki, Aug 17 2011

Links

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

Richard Korf, Linear-time Disk-Based Implicit Graph Search, Journal of the ACM 55 (2008), No. 6.

Anton Kulchitsky, Comments on the Fifteen Puzzle

Tomas Rokicki, Twenty-Four puzzle, some observations, 2011

Formula

From Ben Whitmore, Jul 31 2021: (Start)

a(n) = 2*n^2 + O(n*log(n)).

a(n) >= 2*n^2 - n.

(End)

Crossrefs

Sequence in context: A139606 A047717 A089982 * A207339 A284988 A056488

Adjacent sequences: A151940 A151941 A151942 * A151944 A151945 A151946

Keyword

nonn,hard,more

Author

Anton Kulchitsky (kulchits(AT)arsc.edu), Aug 14 2009, Aug 16 2009

Extensions

a(7)-a(8) from Table III of Richard Korf's work by Tomas Rokicki, Aug 17 2011

Status

approved