cp's OEIS Frontend

A151944 Square array read by antidiagonals: T(m,n) = maximal number of moves required for the m X n generalization of the sliding block 15-puzzle (or fifteen-puzzle).

%I A151944 #24 Jun 08 2024 15:44:33
%S A151944 0,1,1,2,6,2,3,21,21,3,4,36,31,36,4,5,55,53,53,55,5,6,80,84,80,84,80,
%T A151944 6,7,108
%N A151944 Square array read by antidiagonals: T(m,n) = maximal number of moves required for the m X n generalization of the sliding block 15-puzzle (or fifteen-puzzle).
%C A151944 See A087725 for more about this problem and its history.
%H A151944 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 A151944 Anton Kulchitsky, <a href="/A087725/a087725.txt">Comments on the Fifteen Puzzle</a> [The entries for the 3x4 puzzle are wrong.  The second "8" should be "11" in each of the 18 cases.- _Brian Almond_, Oct 10 2021]
%e A151944 Array begins:
%e A151944 .n\m...1...2...3...4...5...6...7...8...9
%e A151944 .----------------------------------------
%e A151944 .1.|...0...1...2...3...4...5...6...7...8
%e A151944 .2.|...1...6..21..36..55..80.108.140
%e A151944 .3.|...2..21..31..53..84
%e A151944 .4.|...3..36..53..80
%e A151944 .5.|...4..55..84
%e A151944 .6.|...5..80
%e A151944 .7.|...6.108
%e A151944 .8.|...7.140
%e A151944 .9.|...8
%o A151944 (Python) # alst(), moves(), swap() in A089473
%o A151944 def T(m, n):  # chr(45) is '-'
%o A151944     start, shape = "".join(chr(45+i) for i in range(m*n)), (m, n)
%o A151944     return len(alst(start, shape))-1
%o A151944 def auptodiag(maxd):
%o A151944     for d in range(1, maxd+1):
%o A151944         for m in range(1, d+1):
%o A151944             n = d-m+1
%o A151944             print(T(m, d-m+1), end=", ")
%o A151944 auptodiag(5) # _Michael S. Branicky_, Aug 02 2021
%Y A151944 Main diagonal: A087725. Row 2: A151943.
%Y A151944 Cf. A090033 same as this sequence, but written as triangle.
%K A151944 nonn,tabl,more
%O A151944 1,4
%A A151944 Anton Kulchitsky (kulchits(AT)arsc.edu), Aug 14 2009, Aug 16 2009
%E A151944 Extensions from Korf's 2008 publication, with corrections, Tomas Rokicki, Aug 17 2011