A090033 Triangle T(j,k) read by rows, where T(j,k) is the number of single tile moves in the longest optimal solution of the j X k generalization of the sliding block 15-puzzle, starting with the empty square in a corner.

0, 1, 6, 2, 21, 31, 3, 36, 53, 80, 4, 55, 84

Offset

1,3

Comments

T(k,j) = T(j,k).

T(2,2), T(2,3), T(4,2), T(4,3) from Karlemo and Östergård, T(3,3) from Reinefeld, T(4,4) from Bruengger et al.

References

For references and links see A087725(n)=T(n,n).

Links

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

Example

The triangle begins
  0
  1   6
  2  21  31
  3  36  53  80
  4  55  84  ...
.
a(6)=T(3,3)=31 because the A090163(3,3)=2 longest optimal solution paths of the 3 X 3 (9-) sliding block puzzle have length 31 (see A089473).

Prog

(Python) # alst(), moves(), swap() in A089473
def T(j, k):  # chr(45) is '-'
    start, shape = "".join(chr(45+i) for i in range(j*k)), (j, k)
    return len(alst(start, shape))-1
for j in range(1, 5):
    for k in range(1, j+1):
        print(T(j, k), end=", ") # Michael S. Branicky, Aug 02 2021

Crossrefs

Cf. A087725, A089473, A089484, A090034, A090035, A090036, A090166, A090163 corresponding number of different configurations with largest distance.

Cf. A151944 same as this sequence, but written as full array.

Sequence in context: A213503 A169632 A201445 * A036173 A142707 A305874

Adjacent sequences: A090030 A090031 A090032 * A090034 A090035 A090036

Keyword

nonn,tabl,hard,more

Author

Hugo Pfoertner, Nov 23 2003

Extensions

T(5,3) copied from A151944 by Hugo Pfoertner, Aug 02 2021

Status

approved