A343146 -id:A343146 - cp's OEIS frontend

A046164 Number of distinct solutions to reverse the 8 puzzle (3 X 3 analog of the 4 X 4 15 puzzle) in 28, 30, 32, ... moves.

0, 10, 112, 512, 2138, 7676, 26034, 87388, 283436, 910035

Offset: 14

From Sean A. Irvine, Apr 06 2021: (Start)
This sequence nominally counts the move sequences that have initial and finite state thus:
  +-+-+-+         +-+-+-+
  |8|7|6|         |1|2|3|
  +-+-+-+         +-+-+-+
  |5|4|3|  --->   |4|5|6|
  +-+-+-+         +-+-+-+
  |2|1| |         |7|8| |
  +-+-+-+         +-+-+-+
but due to an historical accident it appears the shorter solutions have mistakenly been subtracted twice. This means that the number of solutions of length 2n is actually given by a(n) + a(n-1).
A parity argument shows that there can never be a solution of odd length.
A particular solution can visit any state of the puzzle at most once. This means the overall sequence is finite because there is only a finite number of possible states.
(End)

			Concatenating the digits moved at each step, the 10 solutions of length 30 are: 125874312587431631526528741256, 125874852831825743163125741258, 143142587316312587125465487456, 145875365341653412874128741256, 147852478638652471861741521478, 345215435478214786386214758658, 345215764357862176843568421456, 345875134651328713246532487456, 347852174374863865214786521478, 347852178521785643856436421458.

Martin Gardner, The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 206-207, 1984.

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

Cf. A343146.

a(18)-a(23) from Sean A. Irvine, Apr 06 2021

cp's OEIS Frontend

A046164 Number of distinct solutions to reverse the 8 puzzle (3 X 3 analog of the 4 X 4 15 puzzle) in 28, 30, 32, ... moves.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions