VOOZH about

URL: https://oeis.org/A151943

⇱ A151943 - OEIS

login
A151943
Maximal number of moves required for the 2 X n generalization of the sliding block 15-puzzle (or fifteen-puzzle).
2
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
Richard Korf, Linear-time Disk-Based Implicit Graph Search, Journal of the ACM 55 (2008), No. 6.
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
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