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.

%I A046164 #26 Feb 16 2025 08:32:39
%S A046164 0,10,112,512,2138,7676,26034,87388,283436,910035
%N 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.
%C A046164 From _Sean A. Irvine_, Apr 06 2021: (Start)
%C A046164 This sequence nominally counts the move sequences that have initial and finite state thus:
%C A046164   +-+-+-+         +-+-+-+
%C A046164   |8|7|6|         |1|2|3|
%C A046164   +-+-+-+         +-+-+-+
%C A046164   |5|4|3|  --->   |4|5|6|
%C A046164   +-+-+-+         +-+-+-+
%C A046164   |2|1| |         |7|8| |
%C A046164   +-+-+-+         +-+-+-+
%C A046164 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).
%C A046164 A parity argument shows that there can never be a solution of odd length.
%C A046164 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.
%C A046164 (End)
%D A046164 Martin Gardner, The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 206-207, 1984.
%H A046164 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a046/A046164.java">Java program</a> (github)
%H A046164 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/15Puzzle.html">15 Puzzle.</a>
%e A046164 Concatenating the digits moved at each step, the 10 solutions of length 30 are: 125874312587431631526528741256, 125874852831825743163125741258, 143142587316312587125465487456, 145875365341653412874128741256, 147852478638652471861741521478, 345215435478214786386214758658, 345215764357862176843568421456, 345875134651328713246532487456, 347852174374863865214786521478, 347852178521785643856436421458.
%Y A046164 Cf. A343146.
%K A046164 nonn,fini,more
%O A046164 14,2
%A A046164 _Eric W. Weisstein_
%E A046164 a(18)-a(23) from _Sean A. Irvine_, Apr 06 2021