A151944 - OEIS

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

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, 6, 7, 108

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

See A087725 for more about this problem and its history.

LINKS

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

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

Anton Kulchitsky, Comments on the Fifteen Puzzle [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]

EXAMPLE

Array begins:

.n\m...1...2...3...4...5...6...7...8...9

.----------------------------------------

.1.|...0...1...2...3...4...5...6...7...8

.2.|...1...6..21..36..55..80.108.140

.3.|...2..21..31..53..84

.4.|...3..36..53..80

.5.|...4..55..84

.6.|...5..80

.7.|...6.108

.8.|...7.140

.9.|...8

PROG

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

def T(m, n): # chr(45) is '-'

start, shape = "".join(chr(45+i) for i in range(m*n)), (m, n)

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

def auptodiag(maxd):

for d in range(1, maxd+1):

for m in range(1, d+1):

n = d-m+1

print(T(m, d-m+1), end=", ")

auptodiag(5) # Michael S. Branicky, Aug 02 2021

CROSSREFS

Main diagonal: A087725. Row 2: A151943.

Cf. A090033 same as this sequence, but written as triangle.

Sequence in context: A265993 A115009 A378932 * A073094 A194953 A057606

Adjacent sequences: A151941 A151942 A151943 * A151945 A151946 A151947

KEYWORD

nonn,tabl,more

AUTHOR

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

EXTENSIONS

Extensions from Korf's 2008 publication, with corrections, Tomas Rokicki, Aug 17 2011

STATUS

approved