|
| |
|
|
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.
|
|
2
|
|
|
|
1, 2, 8, 40, 228, 1404, 9046, 59892, 403486, 2751104, 18928024, 131178640, 914753916, 6413644272, 45188265984, 319798943360, 2272481584604, 16209083200168, 116019175132958, 833115842931984, 6000491719051994, 43339577695514632, 313846571416413820
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
