A151943 - OEIS

%I #24 Jul 31 2021 07:50:11

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

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

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

%C 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

%H Richard Korf, <a href="https://www.cs.helsinki.fi/u/bmmalone/heuristic-search-fall-2013/Korf2008.pdf">Linear-time Disk-Based Implicit Graph Search</a>, Journal of the ACM 55 (2008), No. 6.

%H Anton Kulchitsky, <a href="/A087725/a087725.txt">Comments on the Fifteen Puzzle</a>

%H Tomas Rokicki, <a href="http://forum.cubeman.org/?q=node/view/238">Twenty-Four puzzle, some observations</a>, 2011

%F From _Ben Whitmore_, Jul 31 2021: (Start)

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

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

%F (End)

%K nonn,hard,more

%O 1,2

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

%E a(7)-a(8) from Table III of Richard Korf's work by _Tomas Rokicki_, Aug 17 2011