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.

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

Author

Sean A. Irvine, Apr 06 2021

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A046164, A089473.