A090033 -id:A090033 - cp's OEIS frontend

A090163 Triangle T(j,k) read by rows, where T(j,K)=number of different configurations having the largest required number of moves S(j,k)=A090033(n) in optimal solutions of the j X k generalization of Sam Loyd's sliding block 15-puzzle, starting with the empty square in a corner.

1, 1, 1, 1, 1, 2, 1, 1, 18

Offset: 1

Hugo Pfoertner, Nov 23 2003

T(k,j)=T(j,k). Extension: a(10)=T(4,4)>=13, a(11)=T(5,1)=1, a(12)=T(5,2)=2.

			a(5)=T(3,2)=1 because the 3*2 sliding block puzzle has only one configuration requiring the maximum solution path length A090033(5)=21.
A090034(21)=1, see link.

Hugo Pfoertner, Solutions of small n*2 sliding block puzzles.

For references, links and cross-references see A087725 and A090033.

A090034 Number of configurations of the 3 X 2 variant of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 10, 12, 12, 16, 23, 25, 28, 39, 44, 40, 29, 21, 18, 12, 6, 1

Offset: 0

Hugo Pfoertner, Nov 23 2003

Data from Karlemo and Östergård. See corresponding link in A087725.

			Starting with
123
45-
the most distant configuration corresponding to a(21)=1 is
45-
123 (i.e., it takes longest just to swap the two rows).

See A087725.

Hugo Pfoertner, Solutions of small n*2 sliding block puzzles.
Takaken, n-Puzzle Page.
Takaken, No. 32 (5 puzzles).

Cf. A087725, A089473, A090033, A090035, A090036, A090163, A090167.

# alst(), moves(), swap() in A089473
print(alst("-12345", (3, 2))) # Michael S. Branicky, Dec 30 2020

A090036 Number of configurations of the 5 X 2 variant of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Original entry on oeis.org

1, 2, 3, 6, 11, 19, 30, 44, 68, 112, 176, 271, 411, 602, 851, 1232, 1783, 2530, 3567, 4996, 6838, 9279, 12463, 16597, 21848, 28227, 35682, 44464, 54597, 65966, 78433, 91725, 104896, 116966, 126335, 131998, 133107, 128720, 119332, 106335, 91545, 75742, 60119, 45840, 33422, 23223, 15140, 9094, 5073, 2605, 1224, 528, 225, 75, 20, 2

Offset: 0

Hugo Pfoertner, Nov 27 2003

			Starting from
12345
6789-
the 2 most distant configurations corresponding to a(55)=2 are
-9371 and -5321
54826.....94876

Hugo Pfoertner, Solutions of small n*2 sliding block puzzles.
Takaken, 11-Puzzle Page.
Takaken, No. 52 (9 puzzles).

Cf. A087725, A089473. Index of last sequence term: A090033. Other nonsquare sliding block puzzles: A090034, A090035, A090166, A090167.

# alst(), moves(), swap() in A089473
print(alst("-123456789", (5, 2))) # Michael S. Branicky, Dec 30 2020

A090035 Number of configurations of the 4 X 2 variant of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Original entry on oeis.org

1, 2, 3, 6, 10, 14, 19, 28, 42, 61, 85, 119, 161, 215, 293, 396, 506, 632, 788, 985, 1194, 1414, 1664, 1884, 1999, 1958, 1770, 1463, 1076, 667, 361, 190, 88, 39, 19, 7, 1

Offset: 0

Hugo Pfoertner, Nov 26 2003

Data from Karlemo, Östergård. See corresponding link in A087725.

			Starting from
1234
567-
the most distant configuration corresponding to a(36)=1 is
-721
4365

See A087725.

Hugo Pfoertner, Solutions of small n*2 sliding block puzzles.
Takaken, n-Puzzle Page.
Takaken, No. 42 (7 puzzles).

Cf. A087725, A089473. Index of last sequence term: A090033. Other nonsquare sliding block puzzles: A090034, A090036, A090166, A090167.

# alst(), moves(), swap() in A089473
print(alst("-1234567", (4, 2))) # Michael S. Branicky, Dec 30 2020

A090167 Number of configurations of the 6 X 2 variant of the so-called "Sam Loyd" sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Original entry on oeis.org

1, 2, 3, 6, 11, 20, 36, 60, 95, 155, 258, 426, 688, 1106, 1723, 2615, 3901, 5885, 8851, 13205, 19508, 28593, 41179, 58899, 83582, 118109, 165136, 228596, 312542, 423797, 568233, 755727, 994641, 1296097, 1667002, 2119476, 2660415, 3300586, 4038877

Offset: 0

Hugo Pfoertner, Nov 27 2003

Herman Jamke, Table of n, a(n) for n = 0..80 (complete sequence)
Hugo Pfoertner, Solutions of small n*2 sliding block puzzles.
Takaken, 11-Puzzle Page.
Takaken, No. 62 (11 puzzles).

Cf. A087725, A089473. Index of last sequence term: A090033. Other nonsquare sliding block puzzles: A090034, A090035, A090036, A090166.

# alst(), moves(), swap() in A089473
alst("-123456789AB", (6, 2), v=True) # Michael S. Branicky, Dec 31 2020

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Oct 22 2006

A090166 Number of configurations of the 4 X 3 variant of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Original entry on oeis.org

1, 2, 4, 9, 20, 37, 63, 122, 232, 431, 781, 1392, 2494, 4442, 7854, 13899, 24215, 41802, 71167, 119888, 198363, 323206, 515778, 811000, 1248011, 1885279, 2782396, 4009722, 5621354, 7647872, 10065800, 12760413, 15570786, 18171606, 20299876, 21587248, 21841159, 20906905, 18899357, 16058335, 12772603, 9515217, 6583181, 4242753, 2503873, 1350268, 643245, 270303, 92311, 27116, 5390, 1115, 86, 18

Offset: 0

Hugo Pfoertner, Nov 27 2003, Jul 07 2007

Data from Karlemo and Östergård.

Filip R. W. Karlemo and Patric R. J. Östergård, On Sliding Block Puzzles, J. Combin. Math. Combin. Comp. 34 (2000), 97-107.
Takaken, 11-Puzzle Page.
Takaken, No. 43 (11 puzzles).

Cf. A087725. Index of last sequence term: A090033. Other nonsquare sliding block puzzles: A090034, A090035, A090036, A090167.

# alst(), moves(), swap() in A089473
alst("-123456789AB", (4, 3), v=True) # Michael S. Branicky, Dec 31 2020

A346736 Number of configurations of the 7 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.

Original entry on oeis.org

1, 2, 3, 6, 11, 20, 37, 67, 117, 198, 329, 557, 942, 1575, 2597, 4241, 6724, 10535, 16396, 25515, 39362, 60532, 92089, 138969, 207274, 307725, 453000, 664240, 964874, 1392975, 1992353, 2832063, 3988528, 5586275, 7756511, 10698721, 14621717, 19840724, 26676629

Offset: 0

Ben Whitmore, Jul 31 2021

This sequence was originally computed by Richard Korf, but the full sequence was not included in his paper. It was later re-computed by Tomas Rokicki.

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

Ben Whitmore, Table of n, a(n) for n = 0..108
Richard Korf, Linear-time Disk-Based Implicit Graph Search, Journal of the ACM 55 (2008), No. 6.
Tomas Rokicki, Twenty-Four puzzle, some observations, 2011.

Cf. A090033, A090034, A090035, A090036, A090167, A089473, A089484.

# alst(), moves(), swap() in A089473
print(alst("-123456789abcd", (7, 2), v=True)) # Michael S. Branicky, Jul 31 2021

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

Original entry on oeis.org

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

Offset: 1

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

See A087725 for more about this problem and its history.

			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

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]

Main diagonal: A087725. Row 2: A151943.

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

# 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

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

A346737 Number of configurations of the 5 X 3 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.

Original entry on oeis.org

1, 2, 4, 9, 21, 42, 89, 164, 349, 644, 1349, 2473, 5109, 9110, 18489, 32321, 64962, 112445, 223153, 378761, 740095, 1231589, 2364342, 3847629, 7246578, 11506172, 21233764, 32854049, 59293970, 89146163, 157015152, 228894783, 392648931, 553489877, 922382155

Offset: 0

Ben Whitmore, Jul 31 2021

This sequence was originally computed by Richard Korf, but the full sequence was not included in his paper. It was later re-computed by Tomas Rokicki.

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

Ben Whitmore, Table of n, a(n) for n = 0..84
Richard Korf, Linear-time Disk-Based Implicit Graph Search, Journal of the ACM 55 (2008), No. 6.
Tomas Rokicki, Twenty-Four puzzle, some observations, 2011.

Cf. A090033, A090034, A090035, A090036, A090167, A346736, A090166, A089473, A089484.

# alst(), moves(), swap() in A089473
print(alst("-123456789abcde", (5, 3), v=True)) # Michael S. Branicky, Jul 31 2021

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.

Original entry on oeis.org

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

Ben Whitmore, Jul 06 2022

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

			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

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.

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

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

cp's OEIS Frontend

A090163 Triangle T(j,k) read by rows, where T(j,K)=number of different configurations having the largest required number of moves S(j,k)=A090033(n) in optimal solutions of the j X k generalization of Sam Loyd's sliding block 15-puzzle, starting with the empty square in a corner.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A090034 Number of configurations of the 3 X 2 variant of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

A090036 Number of configurations of the 5 X 2 variant of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

A090035 Number of configurations of the 4 X 2 variant of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

A090167 Number of configurations of the 6 X 2 variant of the so-called "Sam Loyd" sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A090166 Number of configurations of the 4 X 3 variant of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A346736 Number of configurations of the 7 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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A346737 Number of configurations of the 5 X 3 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.