A089473 -id:A089473 - cp's OEIS frontend

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.

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

A090577 Number of configurations of a variant of the 3-dimensional 3 X 3 X 3 sliding cube puzzle that require a minimum of n moves to be reached, starting with the empty space at one of the enclosing cube corners.

Original entry on oeis.org

1, 3, 9, 24, 72, 174, 519, 1284, 3813, 9300, 27462, 66666, 195674, 470886, 1372946, 3280224, 9495005, 22487511, 64615934, 151714911

Offset: 0

Hugo Pfoertner, Jan 19 2004

The sliding cube 3 X 3 X 3 puzzle under consideration has a fixed central block and 25 movable blocks that can be shifted in the space between the enclosing holder frame and the central block. A description is given in US patents 3845959 and 6513808.

			a(1)=3 because the empty space at one of the 6 corners in the assumed initial configuration can be replaced by any of the 3 adjacent cubes from the middle of the 3 edges meeting at the empty corner in the first move.

Chih Chung Fang, Cubic Puzzle. US Patent 6513808, filed May 09, 2001
Daniel Kosarek, Three-dimensional block puzzle. US Patent 3845959, filed Nov. 5, 1974

Cf. A090578, A091521 this puzzle with different initial configurations, A090572 2X2X2 puzzle, A090573 - A090576 configurations of the 3 X 3 X 3 puzzle with 26 movable blocks.

# uses alst(), swap() in A089473, moves3d() in A090573
moves = lambda p, shape: moves3d(p, shape, fixed=13)
start, shape = "-123456789ABCDEFGHIJKLMNOPQ", (3, 3, 3)
print(alst(start, shape, maxd=14)) # Michael S. Branicky, Dec 28 2020

a(15)-a(19) from Michael S. Branicky, Dec 28 2020

A091521 Number of configurations of a variant of the 3-dimensional 3 X 3 X 3 sliding cube puzzle that require a minimum of n moves to be reached, starting with the empty space at the center of one of the 6 faces of the combination cube.

Original entry on oeis.org

1, 4, 12, 28, 84, 212, 632, 1544, 4584, 11220, 33060, 80152, 234648, 565192, 1643552, 3926832, 11337422, 26852656, 76981660

Offset: 0

Hugo Pfoertner, Jan 19 2004

See under A090577.

			a(1)=4 because the empty space located at the center of a face of the combination cube in the assumed initial configuration can be replaced in the first move by one of the 4 adjacent cubes located at the edges of the face initially containing the empty space. The cube at the center of the combination cube cannot replace the empty space because the construction of this puzzle inhibits the movement of the central cube.

Cf. A090577, A090578 this puzzle with different initial configurations, A090572 2 X 2 X 2 puzzle, A090573 - A090576 configurations of the 3 X 3 X 3 puzzle with 26 movable blocks.

# uses alst(), swap() in A089473, moves3d() in A090573
moves = lambda p, shape: moves3d(p, shape, fixed=13)
start, shape = "1234-56789ABCDEFGHIJKLMNOPQ", (3, 3, 3)
print(alst(start, shape, maxd=13)) # Michael S. Branicky, Dec 28 2020

a(14)-a(18) from Michael S. Branicky, Dec 28 2020

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

A343146 Number of move sequences of length 2n on the "8 Puzzle" which leave the final state unchanged when the empty cell starts in a corner.

Original entry on oeis.org

1, 2, 8, 40, 228, 1404, 9046, 59892, 403486, 2751104, 18928024, 131178640, 914753916, 6413644272, 45188265984, 319798943360, 2272481584604, 16209083200168, 116019175132958, 833115842931984, 6000491719051994, 43339577695514632, 313846571416413820

Offset: 0

Sean A. Irvine, Apr 06 2021

nonn

The "8 Puzzle" is the 3 X 3 analog of the "15 Puzzle". This sequence counts the possible move sequences of length 2n which leaves the puzzle in an unchanged state when starting from the following state:
  +---+---+---+
  | 1 | 2 | 3 |
  +---+---+---+
  | 4 | 5 | 6 |
  +---+---+---+
  | 7 | 8 |   |
  +---+---+---+
A move consists of "sliding" a tile adjacent to the empty space into the empty space.
A parity argument shows that it is not possible for an odd number of moves to leave the state unchanged.
Unlike A046164, a given state (including the start state) is allowed to repeat an arbitrary number of times in a given move sequence (e.g., repeatedly moving a number backward or forward is permitted).

			a(0)=1 because doing nothing leaves the puzzle in the identity state.
a(1)=2 because 66 and 88 leave the puzzle in the identity state (concatenating together the numbers moved to indicate the move sequence).
a(2)=8 by the sequences 6666, 6688, 8866, 8888, 6336, 8778, 6556, 8558.
More complicated move sequences occur for larger n.

Sean A. Irvine, Java program (github)
Eric Weisstein's World of Mathematics, 15 Puzzle.

Cf. A046164, A089473.

A090378 Number of configurations that require a minimum of n moves to be reached, starting with the empty square at mid-side of a boundary of an infinitely large extension of Sam Loyd's sliding block 15-puzzle.

Original entry on oeis.org

1, 3, 7, 19, 53, 147, 409, 1151, 3255, 9241, 26267, 74895, 213775, 611463, 1750277, 5017901

Offset: 0

Hugo Pfoertner, Nov 27 2003

Next term (unconfirmed): a(6)=409. If started with the empty square at mid-side of a boundary, the number of configurations reachable in the first floor((n-1)/2) moves in an n X n sliding block puzzle are given by this sequence.

Cf. A089483 (3 X 3 puzzle started with empty square at mid-side), A090165.

# uses alst(), swap() in A089473
nn = 24
mid = (nn-1)//2
startlst = [chr(i) for i in range(45, 45+nn**2)] # chr(45) is "-"
startlst[0], startlst[mid] = startlst[mid], startlst[0]
start = "".join(startlst)
print(alst(start, (nn, nn), maxd=mid)) # Michael S. Branicky, Jan 02 2021

a(6) confirmed and a(7)-a(15) from Michael S. Branicky, Dec 28 2020

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

A090377 Number of configurations that require a minimum of n moves to be reached, starting with the empty square in one of the corners of an infinitely large extension of Sam Loyd's sliding block 15-puzzle.

Original entry on oeis.org

1, 2, 4, 10, 26, 66, 173, 456, 1230, 3318, 9066, 24768, 68304, 188370, 523083, 1452560, 4054708, 11318926

Offset: 0

Hugo Pfoertner, Nov 27 2003

The first n terms of this sequence coincide with the first n terms of the corresponding sequences for n X n sliding block puzzles (see Cross-references).

Cf. A089473 (3 X 3 puzzle), A089484 (4 X 4), A090031 (5 X 5), A090032 (6 X 6).

# uses alst(), swap() in A089473
nn = 13
start = "".join([chr(i) for i in range(45, 45+(nn+1)**2)]) # chr(45) is "-"
print(alst(start, (nn+1, nn+1), maxd=nn)) # Michael S. Branicky, Jan 02 2021

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

cp's OEIS Frontend

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

A090577 Number of configurations of a variant of the 3-dimensional 3 X 3 X 3 sliding cube puzzle that require a minimum of n moves to be reached, starting with the empty space at one of the enclosing cube corners.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A091521 Number of configurations of a variant of the 3-dimensional 3 X 3 X 3 sliding cube puzzle that require a minimum of n moves to be reached, starting with the empty space at the center of one of the 6 faces of the combination cube.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

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

A343146 Number of move sequences of length 2n on the "8 Puzzle" which leave the final state unchanged when the empty cell starts in a corner.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A090378 Number of configurations that require a minimum of n moves to be reached, starting with the empty square at mid-side of a boundary of an infinitely large extension of Sam Loyd's sliding block 15-puzzle.

Views

Author

Keywords

Comments

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A090377 Number of configurations that require a minimum of n moves to be reached, starting with the empty square in one of the corners of an infinitely large extension of Sam Loyd's sliding block 15-puzzle.