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