A355560 Number of configurations of the 8 X 2 variant of the sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

1, 2, 3, 6, 11, 20, 37, 68, 125, 227, 394, 672, 1151, 1983, 3373, 5703, 9508, 15640, 25293, 40732, 65032, 103390, 162830, 255543, 397013, 613104, 938477, 1431068, 2162964, 3255845, 4860428, 7223861, 10649867, 15628073, 22747718, 32963838, 47397514, 67825949, 96317070

Offset

0,2

Comments

This sequence was computed by Richard Korf in "Linear-time Disk-Based Implicit Graph Search" (see links), but was not included in the paper.

Links

Ben Whitmore, Table of n, a(n) for n = 0..140

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

Example

Starting from the solved configuration
   1  2  3  4  5  6  7  8
   9 10 11 12 13 14 15
the unique configuration requiring 140 moves is
      8  6  5  4  3 10  1
  15  7 14 13 12 11  2  9

Prog

(Python) # alst(), moves(), swap() in A089473
print(alst("-123456789abcdef", (8, 2), v=True)) # Michael S. Branicky, Jul 06 2022

Crossrefs

Cf. A090033, A090034, A090035, A090036, A090167, A346736.

Sequence in context: A358709 A346736 A335628 * A001590 A078042 A047081

Adjacent sequences: A355557 A355558 A355559 * A355561 A355562 A355563

Keyword

nonn,fini,full

Author

Ben Whitmore, Jul 06 2022

Status

approved