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

Author

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

Keywords

• nonn
• hard
• more

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.
• 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)

Extensions

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