login
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.
10

%I #24 Aug 02 2021 06:41:03

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

%N 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.

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

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

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

%e The triangle begins

%e 0

%e 1 6

%e 2 21 31

%e 3 36 53 80

%e 4 55 84 ...

%e .

%e 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).

%o (Python) # alst(), moves(), swap() in A089473

%o def T(j, k): # chr(45) is '-'

%o start, shape = "".join(chr(45+i) for i in range(j*k)), (j, k)

%o return len(alst(start, shape))-1

%o for j in range(1, 5):

%o for k in range(1, j+1):

%o print(T(j,k), end=", ") # _Michael S. Branicky_, Aug 02 2021

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

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

%K nonn,tabl,hard,more

%O 1,3

%A _Hugo Pfoertner_, Nov 23 2003

%E T(5,3) copied from A151944 by _Hugo Pfoertner_, Aug 02 2021