A087725 -id:A087725 - cp's OEIS frontend

A090032 Number of configurations of the 6 X 6 variant of Sam Loyd's sliding block 15-puzzle ("35-puzzle") that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

1, 2, 4, 10, 26, 66, 171, 440, 1112, 2786, 6820, 16720, 41106, 100856, 245793, 597030, 1441292, 3469486, 8304526, 19832076, 47110238, 111669014

Offset: 0

Hugo Pfoertner, Nov 25 2003

See A087725.

Hugo Pfoertner, Configuration counts for n*n sliding block puzzles.

Cf. A087725, A089473, A089484, A090031.

# uses alst(), swap() in A089473
start, shape = "-123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ", (6, 6)
print(alst(start, shape, maxd=16)) # Michael S. Branicky, Jan 02 2021

a(17)-a(21) from Michael S. Branicky, Dec 28 2020

A090165 Number of configurations of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square at one of the 8 non-corner boundary squares.

Original entry on oeis.org

1, 3, 6, 14, 32, 66, 134, 280, 585, 1214, 2462, 4946, 9861, 19600, 38688, 76086, 148435, 288098, 554970, 1062628, 2016814, 3800682, 7093209, 13127364, 24053454, 43657576, 78382622, 139237375

Offset: 0

Hugo Pfoertner, Nov 27 2003

Cf. A087725, A089473, A089484, A090164, A090378.

# uses alst(), swap() in A089473
start, shape = "1-23456789ABCDEF", (4, 4)
print(alst(start, shape, maxd=16)) # Michael S. Branicky, Jan 02 2021

a(17)-a(27) from Michael S. Branicky, Dec 28 2020

A089474 Number of configurations of the sliding block 8-puzzle that require a minimum of n moves to be reached, starting with the empty square in the center.

Original entry on oeis.org

1, 4, 8, 8, 16, 32, 60, 72, 136, 200, 376, 512, 964, 1296, 2368, 3084, 5482, 6736, 11132, 12208, 18612, 18444, 24968, 19632, 22289, 13600, 11842, 4340, 2398, 472, 148

Offset: 0

Hugo Pfoertner, Nov 19 2003

			Starting with
123
4-5
678
two of the 148 configurations that require the maximum of 30 moves are
476 ... -86
2-8 and 724
351 ... 351

See A087725.

Hugo Pfoertner, Table of solution lengths of the 8-puzzle

Cf. A089473, A089483, A089484, A087725, A090031.

Maple
```
See link in A089473.
```

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

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.

Original entry on oeis.org

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.

A090164 Number of configurations of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square at one of the 4 central squares.

Original entry on oeis.org

1, 4, 10, 20, 38, 80, 174, 372, 762, 1540, 3072, 6196, 12356, 24516, 48179, 94356, 183432, 355330, 682250, 1301874, 2460591, 4617322, 8580175, 15815664, 28854386, 52154316, 93214030

Offset: 0

Hugo Pfoertner, Nov 27 2003

Cf. A087725, A089484, A090165.

Maple
```
See link in A089473.
```

# uses alst(), swap() in A089473
start, shape = "12345-6789ABCDEF", (4, 4)
print(alst(start, shape, maxd=15)) # Michael S. Branicky, Jan 02 2021

a(16)-a(26) from Michael S. Branicky, Dec 28 2020

A151943 Maximal number of moves required for the 2 X n generalization of the sliding block 15-puzzle (or fifteen-puzzle).

Original entry on oeis.org

1, 6, 21, 36, 55, 80, 108, 140

Offset: 1

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

See A087725 for more about this problem and its history. See also A151944.

Three corrections to table III of the Korf reference: the radius of the 2 X 4 should be 36; the depth of the 3 X 5 should be 52, and the ratio of the 3 X 5 should be 14.379. - Tomas Rokicki, Aug 17 2011

Richard Korf, Linear-time Disk-Based Implicit Graph Search, Journal of the ACM 55 (2008), No. 6.
Anton Kulchitsky, Comments on the Fifteen Puzzle
Tomas Rokicki, Twenty-Four puzzle, some observations, 2011

From Ben Whitmore, Jul 31 2021: (Start)
a(n) = 2*n^2 + O(n*log(n)).
a(n) >= 2*n^2 - n.
(End)

a(7)-a(8) from Table III of Richard Korf's work by Tomas Rokicki, Aug 17 2011

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

A264040 Number of possible permutations of the n X n generalization of the sliding block 15-puzzle.

Original entry on oeis.org

1, 12, 181440, 10461394944000, 7755605021665492992000000, 185996663394950608733999724075417600000000, 304140932017133780436126081660647688443776415689605120000000000, 63443466092942082051716694667580740401432758087272596099400947187607352115200000000000000

Offset: 1

Ben Whitmore, Nov 01 2015

For n > 1, of the permutations that can be reached by disassembling the puzzle and replacing the tiles, exactly half of them can be reached by sliding the tiles.

			a(4) = 10461394944000 because the standard 4 X 4 version of the 15-puzzle has exactly 10461394944000 permutations that can be reached by sliding the tiles.

Eric Weisstein's World of Mathematics, 15 Puzzle

Cf. A087725, A090031, A088020.

Mathematica
```
a[n_] := If[n == 1, 1, (n^2)!/2]
```

a(1) = 1; a(n) = (n^2)!/2 for n > 1.

a(1) added by Franklin T. Adams-Watters, Nov 11 2015

cp's OEIS Frontend

A090032 Number of configurations of the 6 X 6 variant of Sam Loyd's sliding block 15-puzzle ("35-puzzle") that require a minimum of n moves to be reached, starting with the empty square in one of the corners.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

Extensions

A090165 Number of configurations of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square at one of the 8 non-corner boundary squares.

Views

Author

Keywords

Crossrefs

Programs

Python

Extensions

A089474 Number of configurations of the sliding block 8-puzzle that require a minimum of n moves to be reached, starting with the empty square in the center.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Python

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

A090164 Number of configurations of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square at one of the 4 central squares.

Views

Author

Keywords

Crossrefs

Programs

Maple

Python

Extensions

A151943 Maximal number of moves required for the 2 X n generalization of the sliding block 15-puzzle (or fifteen-puzzle).

Views

Author

Keywords

Comments

Links

Formula

Extensions

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

A264040 Number of possible permutations of the n X n generalization of the sliding block 15-puzzle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions