The 15-puzzle groupoid (1)

Before we go deeper into Conway’s M(13) puzzle, let us consider a more commonly known sliding puzzle: the 15-puzzle. A heated discussion went on a couple of years ago at sci-physics-research, starting with this message. Lubos Motl argued that group-theory is sufficient to analyze the problem and that there is no reason to resort to groupoids (‘The human(oids) who like groupoids…’ and other goodies, in pre-blog but vintage Motl-speak) whereas ‘Jason’ defended his viewpoint that a groupoid is the natural symmetry for this puzzle.

I’m mostly with Lubos on this. All relevant calculations are done in the symmetric group $S_{16} $ and (easy) grouptheoretic results such as the distinction between even and odd permutations or the generation of the alternating groups really crack the puzzle. At the same time, if one wants to present this example in class, one has to be pretty careful to avoid confusion between permutations encoding positions and those corresponding to slide-moves. In making such a careful analysis, one is bound to come up with a structure which isn’t a group, but is precisely what some people prefer to call a groupoid (if not a 2-group…).

Groupoids are no recent invention but date back to 1926 when Heinrich Brandt defined what we now know as the ‘Brandt groupoid’ in his study of _noncommutative number theory_. He was studying central simple algebras (the noncommutative counterpart of number fields) in which there usually is not a unique ‘ring of integers’ (in noncommutative parlance, a maximal order) and fractional ideals have a left- and a right- maximal order associated to it, leading naturally to left- and right- unit elements and the notion of a groupoid.

The algebraic notion of a groupoid is a set G with a partial multiplication and an everywhere defined inverse satisfying associativity $a \ast (b \ast c) = (a \ast b) \ast c $ whenever the terms are defined. Further, whenever $ a \ast b $ is defined one has $ a^{-1} \ast a \ast b = b $ and $a \ast b \ast b^{-1} = a $ and finally all $a^{-1} \ast a $ and $ a \ast a^{-1} $ are defined (but may be different elements). The categorical definition of a groupoid is even simpler : it is a category in which every morphism is an isomorphism. Both notions are equivalent.

Recall that the 15-puzzle is a 4×4 slide-puzzle with initial configuration with the hole at the right bottom square (see left) and one can slide the hole one place at a time in vertical or horizontal direction. For example, if one slides the hole along the path 12-11-7-6-2 one ends up with the situation on the right

$\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\
\hline 5 & 6 & 7 & 8 \\ \hline 9 & 10 & 11 & 12 \\ \hline 13 & 14 & 15 & \\ \hline \end{array} $ (initial position)
$\begin{array}{|c|c|c|c|} \hline 1 & & 3 & 4 \\
\hline 5 & 2 & 6 & 8 \\ \hline 9 & 10 & 7 & 11 \\ \hline 13 & 14 & 15 & 12 \\ \hline \end{array} $ (position after 12-11-7-6-2)

The mathematical aim is to determine the allowed positions, that is those which can be reached from the initial position by making legal slide moves. The puzzle aim is to return to the initial position starting from an allowed position. We will determine the number of allowed positions and why they are the elements of a groupoid.

We dont want to draw arrays all the time so we need a way to encode a position. Giving the hole label 16 we can record a position by writing down the permutation on 16 letters describing by which label in the given position, the label of the initial position is replaced. For example, the situation on the right arises by leaving 1 to position 1, 2 is replaced by 16, 3,4 and 5 are left in their position but 6 is replaced by 2 and so on. So, we can encode this position by the permutation
$\sigma = (2,16,12,11,7,6) $ and conversely, given such a permutation we can fill in the entire position encoded by it. We will denote the array or position corresponding to a partition $\tau \in S_{16} $ by the boxed symbol $\boxed{\tau} $.

Next, we turn to slide-moves. A basic move interchanges the hole (label 16) with a square labeled i (if i is a horizontal or vertical neighbor of the hole in the position) so can be represented by the transposition $~(16,i) $. We can iterate this procedure, a legal move from a position $\boxed{\tau} $ will be a succession of basic-moves written from right to left as is usual in composing permutations

$~(16,i_k) \cdots (16,i_2)(16,i_1) $

where legality implies that at each step the label $i_{m+1} $ must be a vertical or horizontal neighbor of the hole in the position reached from $\boxed{\tau} $ after applying the move $~(16,i_m)(16,i_{m-1}) \cdots (16,i_2)(16,i_1) $. Hence, we’d better have a method to compute the position we obtain from a given position by applying a legal sequence of slide-moves. The rule is : multiply the slide-move-permutation with the position-permutation in the group $S_{16} $ to get the code for the obtained position. In symbols

$~(16,i_k) \cdots (16,i_2)(16,i_1) \boxed{\tau} = \boxed{(16,i_k) \cdots (16,i_2)(16,i_1) \tau} $

For example, the initial position corresponds to the identity permutation, that is, is $\boxed{()} $ and applying to it the legal seuence of slides moved along the path 12-11-7-6-2 as before we get the position with code

$~(16,2)(16,6)(16,7)(16,11)(16,12) \boxed{()} = \boxed{(16,2)(16,6)(16,7)(16,11)(16,12)} = \boxed{(16,12,11,7,6,2)} $

which is indeed the code of the position obtained above on the right. Right, the basic ingredient to have full understanding of this puzzle are hence the combination of an allowed position together with a legal move-sequence starting from it. Therefore, we will take as our elements all possible combinations $\sigma \boxed{\tau} $ with $\sigma,\tau \in S_{12} $ where $\tau $ is the code of a reachable position and $\sigma = (16,i_l) \cdots (16,i_1) $ is a legal move from that position.

On this set of elements we only have a partially defined composition rule, for we can only make sense of the composition of moves

$\sigma_1 \boxed{\tau_1} \ast \sigma_2 \boxed{\tau_2} = \sigma_1 \sigma_2 \boxed{\tau_2} $

provided $\tau_1 $ is the code of the position reached from $\boxed{\tau_2} $ after applying the move-sequence $\sigma_2 $, that is, the multiplication above is defined if and only if

$\tau_1 = \sigma_2 \tau_2 $ in $S_{16} $

All conditions of the algebraic notion of a groupoid are satisfied. For example, every element has an inverse

$~(\sigma \boxed{\tau})^{-1} = \sigma^{-1} \boxed{\omega} $ where $\omega = \sigma \tau $ in $S_{16} $

and it is easy to check that all conditions are indeed satisfied. In the categorical definition, the groupoid is the category having as the objects the reachable positions, and morphisms $\boxed{\tau_1} \rightarrow \boxed{\tau_2} $ are of the form $\sigma_1 \boxed{\tau_1} $ such that $\sigma_1 \tau_1 = \tau_2 $ (hence, all morphisms are isomorphisms and there is just one morphism between two objects, namely corresponding to $\sigma_1 = \tau_2 \tau_1^{-1} \in S_{16} $. For example, each object $\boxed{\tau} $ also has an identity morphism $~() \boxed{\tau} $ and again all categorical requirements are met.

This groupoid we will call the the 15-puzzle groupoid and next time we will determine that it has exactly $\frac{1}{2} 16! $ objects.

One thought on “The 15-puzzle groupoid (1)”

  1. In implementing a computer simulation of the 15 puzzle I have found that it is possible to map the legal
    positions of the puzzle 1:1 to a permutation group. This makes a groupoid treatment unnecessary.

    Key to the approach is a toroidal mapping of the puzzle grid. The columns and rows wrap such that moving
    four spaces in any cardinal direction takes one back to the original position. Any state of the puzzle may be
    converted to a state with the void token (token 16) in position 16 by rolling the columns and rows right and down.
    For example:
    15 12 7 1 ⇒ 1 15 12 7 ⇒ 9 2 6 11
    14 10 16 5 ⇒ 5 14 10 16 ⇒ 13 3 4 8
    2 6 11 9 ⇒ 9 2 6 11 ⇒ 1 15 12 7
    3 4 8 13 ⇒ 13 3 4 8 ⇒ 5 14 10 16

    Given a toroidal mapping of the grid, the above rearrangement may be seen as a simple translation of the origin. As such the
    essential metric of the token positions is preserved. Tokens 1 through 15 in the rearranged tableau define a permutation. In GAP cycle notation:

    (1,9)(3,6)(4,11,12,7)(5,13)(10,15)

    This permutation gives the arrangement of the tokens relative to the void token. The representation is completed with two cyclic
    permutation groups of order 4.
    These may be viewed simply as counters giving the number of positions left and up the origin has been shifted.

    (1,9)(3,6)(4,11,12,7)(5,13)(10,15) * (16,18)(17,19) * (20,21,22,23)

    where up 1 = (16,17,18,19) and left 1 = (20,21,22,23)

    It is easily seen that any arrangement of tokens in the fifteen puzzle may be uniquely an unambiguously translated into a permutation of this form. The legal
    moves of the puzzle involve swapping the void token with an adjacent token. These moves may be modeled by applying one of the following
    permutations to the state’s representation.

    L := (1,4,3,2)(5,8,7,6)(9,12,11,10)(13,15,14)(20,21,22,23);
    R := (1,2,3,4)(5,6,7,8)(9,10,11,12)(13,14,15)(20,23,22,21);
    U := (1,13,9,5)(2,14,10,6)(3,15,11,7)(4,12,8)(16,17,18,19);
    D := (1,5,9,13)(2,6,10,14)(3,7,11,15)(4,8,12)(16,19,18,17);

    where L swaps the void token with the token to the left, etc.

    Given this assertion(evident on inspection), all states of the puzzle may be modeled by products of the above generators. The remaining issue is that the
    above generators may be applied in ways inappropriate to the physical puzzle. R applied to the identity position swaps the void token with the
    token in position 13:

    1 2 3 4
    5 6 7 8
    9 10 11 12
    16 14 15 13

    It can be shown that all of these swaps beyond the edges of the puzzle may be accomplished with legal puzzle moves. For example, the above position may
    be arrived at by the move sequence, L L L U R D R R U L L L D R R U R D L L L. Thus, all products formed from the above generators represent legal puzzle positions.
    And therefore, the group formed from the above generators is a well formed model of the 15 puzzle.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>