OFFSET
0,2
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).
LINKS
Sean A. Irvine, Java program (github)
Eric Weisstein's World of Mathematics, 15 Puzzle.
EXAMPLE
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.
CROSSREFS
KEYWORD
nonn
AUTHOR
Sean A. Irvine, Apr 06 2021
STATUS
approved