|
|
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.
|
|
3
|
|
|
|
OFFSET
|
14,2
|
|
COMMENTS
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|