The 15-puzzle groupoid (2)

In the 15-puzzle groupoid 1 we have seen that the legal positions of the classical 15-puzzle are the objects of a category in which every morphism is an isomorphism (a groupoid ). Today, we will show that there are exactly 10461394944000 objects (legal positions) in this groupoid. The crucial fact is that positions with the hole in a fixed place can be identified with the elements of the alternating group $A_{15}$, a fact first proved by William Edward Story in 1879 in a note published in the American Journal of Mathematics.

Recall from last time that the positions reachable from the initial position can be encoded as $\boxed{{\displaystyle \tau }}$ where $\tau$ is the permutation on 16 elements (the 15 numbered squares and 16 for the hole) such that $\tau (i)$ tells what number in the position lies on square $i$ of the initial position. The set of all reachable positions are the objects of our category. A morphism $\boxed{{\displaystyle \tau }}\to \boxed{{\displaystyle \sigma }}$ is a legal sequence of slide-moves starting from position $\boxed{{\displaystyle \tau }}$ and ending at position $\boxed{{\displaystyle \sigma }}$. That is,

$\boxed{{\displaystyle \sigma }}=(16,i_k)(16,i_{k-1})\cdots (16,i_2)(16,i_1)\boxed{{\displaystyle \tau }}$

where for every number m between 1 and k we have that the number $i_{m+1}$ is an horizontal or vertical neighbor of the hole in position $\boxed{{\displaystyle (16,i_m)\cdots (16,i_1)\tau }}$. When we identify such a morphism with the corresponding element $(16,i_k)\cdots (16,i_2)(16,i_1)\in S_{16}$ we see that it must be the unique element $\sigma {\tau }^{-1}$ hence there is just one morphism between two objects and they are all invertible, so our category is indeed a groupoid. Can we say something about the length k of such a sequence of slide moves? Well, consider the OXO-drawing on our 4×4 square

$\begin{array}{|cccc|}\hline O& X& O& X\\ X& O& X& O\\ O& X& O& X\\ X& O& X& O\\ \hline\end{array}$

One legal slide-move brings an O-hole to an X-hole and an X-hole to an O-hole, so if the holes in $\boxed{{\displaystyle \sigma }}$ and $\boxed{{\displaystyle \tau }}$ are of the same type (both O-holes or both X-holes) then the length k of a legal sequence must be even and therefore the permutation $\sigma {\tau }^{-1}=(16,i_k)\cdots (16,i_1)$ belongs to the simple alternating group $A_{16}$.

In particular, if we take $\tau =()$ the original position we see that if a reachable position $\sigma$ has the hole in the bottom right corner (and hence $\sigma$ fixes 16 so is an element of $S_{15}$) then

$\sigma \in A_{16}\cap S_{15}=A_{15}$

and in particular, Loyd’s 14-15 puzzle has no solution (as it corresponds to the transposition $\sigma =(14,15)\notin A_{15}$. This argument first appeared in print in W.W. Johnson “Note on the “15” puzzle” Amer. J. Math. 2 (1879) 397-399. We can compose legal sequences leading to positions having their hole at the bottom right in the groupoid showing that such positions can be identified with a subgroup of $A_{15}$. Note that we do NOT claim that we can multiply any two sequences of even length $(16,i_k)\cdots (16,i_1)$ with $(16,j_l)\cdots (16,j_1)$ (which would give us the whole of $A_{16}$) but only composable morphisms in the groupoid!

W.E. Story then went on to show that this subgroup is the full alternating group $A_{15}$ which comes down to finding enough reachable positions, with the hole at the bottom right, to generate the group. We will sketch a more recent argument due to Aaron Archer (Math. Monthly 106 (1999) 793-799). He starts out with another encoding of reachable positions, disregarding the exact placement of the hole. He records the 15-numbers in order along a snakelike path disregarding the hole.

$\begin{array}{|cccc|}\hline \to & \to & \to & \downarrow \\ \downarrow & \leftarrow & \leftarrow & \leftarrow \\ \to & \to & \to & \downarrow \\ \leftarrow & \leftarrow & \leftarrow & \leftarrow \\ \hline\end{array}$ so the position $\begin{array}{|cccc|}\hline 1& 2& 3& 4\\ 5& 6& 7& 8\\ & 15& 12& 14\\ 13& 9& 11& 10\\ \hline\end{array}$

is encoded as $[1,2,3,4,8,7,6,5,15,12,14,10,11,9,13]$. The point being that we can slide the hole along the snakelike path to get a uniquely determined position having the same code but with the hole at another position. For example, sliding the hole along the path upwards to the third square of the upper row we get the position

$\begin{array}{|cccc|}\hline 1& 2& & 3\\ 6& 7& 8& 4\\ 5& 15& 12& 14\\ 13& 9& 11& 10\\ \hline\end{array}$ having the same code.

This gives a natural one-to-one correspondence between reachable positions having their hole at spot i with those having the hole on spot j, so in order to determine the number of objects in our groupoid, it suffices to count the number of reachable positions with the hole at a specified spot. They are just all the codes and as they form a subgroup of $A_{15}$ it is enough to calculate the permutations induced on a code by just one slide-move. If the slide move is along the snakelike path, it will not alter the code, so we only have to compute 9 remaining slide modes S(1,8), S(2,7), S(3,6), S(7,10), S(6,11), S(5,12), S(9,16), S(10,15) and S(11,14) where the numbers correspond to the order in which we encounter the square along the snakelike path. For example S(1,8) is the slide move changing the hole at position (1,1) to position (2,1). This move has the following effect on a position

$\begin{array}{|cccc|}\hline & a_1& a_2& a_3\\ a_7& a_6& a_5& a_4\\ a_8& a_9& a_{10}& a_{11}\\ a_{15}& a_{14}& a_{13}& a_{12}\\ \hline\end{array}$ moving to $\begin{array}{|cccc|}\hline a_7& a_1& a_2& a_3\\ & a_6& a_5& a_4\\ a_8& a_9& a_{10}& a_{11}\\ a_{15}& a_{14}& a_{13}& a_{12}\\ \hline\end{array}$

whence it has the effect of changing the code

$[a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10},a_{11},a_{12},a_{13},a_{14},a_{15}]$ to the code

$[a_7,a_1,a_2,a_3,a_4,a_5,a_6,a_8,a_9,a_{10},a_{11},a_{12},a_{13},a_{14},a_{15}]$

and therefore it corresponds to the permutation $S(1,8)=(1,7,6,5,4,3,2)$. Similarly, one calculates that the other slide moves determine the following permutations

$S(2,7)=(2,6,5,4,3),S(3,6)=(3,5,4),S(5,12)=(5,11,10,9,8,7,6)$

$S(6,11)=(6,10,9,8,7),S(7,10)=(7,9,8),S(9,16)=(9,15,14,13,12,11,10)$

$S(10,15)=(10,14,13,12,11),S(11,14)=(11,13,12)$

(Ive replaced the permutations in Archer’s paper by their inverses because I want to have left actions rather than right ones). The only thing left to do is to fire up GAP (update : or use Michel’s comment below) and verify that these permutations do indeed generate the full alternating group $A_{15}$. Summarizing, there are precisely $\frac{1}{2}15!$ reachable positions having their hole in a specified place and as there are 16 possible places for the hole, we get that the total number of reachable positions (or if you prefer, the number of objects in our groupoid) is equal to

$16\times \frac{1}{2}15!=\frac{1}{2}16!=10461394944000$

and the whole point of the careful group versus groupoid analysis is that one should not make the mistake in interpreting this number as the number of elements of the alternating group $A_{16}$. For those who don’t like categories but prefer the algebraic notion of a groupoid, their groupoid has

$(10461394944000{)}^2=109440784174348763136000000$

elements as there is exactly one morphism between two objects.

References

Aaron F. Archer, “A Modern Treatment of the 15 Puzzle” Mathematical Monthly 106 (1999) 793-799

W.E. Story, “Note on the “15” puzzle”, Amer. J. Math. 2 (1879) 399-404