OFFSET
14,2
COMMENTS
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)
REFERENCES
Martin Gardner, The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 206-207, 1984.
LINKS
Sean A. Irvine, Java program (github)
Eric Weisstein's World of Mathematics, 15 Puzzle.
EXAMPLE
Concatenating the digits moved at each step, the 10 solutions of length 30 are: 125874312587431631526528741256, 125874852831825743163125741258, 143142587316312587125465487456, 145875365341653412874128741256, 147852478638652471861741521478, 345215435478214786386214758658, 345215764357862176843568421456, 345875134651328713246532487456, 347852174374863865214786521478, 347852178521785643856436421458.
CROSSREFS
KEYWORD
nonn,fini,more
AUTHOR
EXTENSIONS
a(18)-a(23) from Sean A. Irvine, Apr 06 2021
STATUS
approved