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,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

Table of n, a(n) for n=14..23.

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

Cf. A343146.

Sequence in context: A066275 A362671 A344398 * A322724 A184131 A239651

Adjacent sequences: A046161 A046162 A046163 * A046165 A046166 A046167

Keyword

nonn,fini,more

Author

Eric W. Weisstein

Extensions

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

Status

approved