Making waffles with group theory · hmpc

A few years back, some time after the Wordle craze abated, I found a new word game called Waffle and promptly got hooked. If you’ve never played it before, I highly recommend trying it out before reading the rest of this post.

Waffle 101

Waffle, created by James Robinson, is a sort of crossword-shaped jigsaw puzzle with 21 letters in a five by five grid. The goal is to reconstruct the six original words, corresponding to the full rows and columns of the grid, by swapping two letters at a time. The game provides hints through the colour of each tile: grey if that letter does not belong in that row or column, yellow if it belongs there but in a different position¹, and green if it’s correctly placed. Looking at a few Waffles, you might also notice that the corners and centre of the grid are always helpfully pre-solved for us.

You can use up to 15 moves to solve each Waffle, but all of them are solvable in only 10 moves. Your score is the number of remaining swaps, up to a maximum of five. There is also a weekly Waffle Deluxe with a seven by seven grid and 12 pre-solved tiles, solvable in 20 moves with a limit of 25.

The puzzle behind the puzzle

After playing my way through the entire Waffle archive I had a pretty good understanding of the optimal solving strategy, but I was more interested in the other side of the puzzle: how to generate Waffles that were guaranteed to be solvable in exactly ten moves, no more and no less. Doing ten random swaps on the original board is not enough to guarantee it: trivially, we could just swap the same two tiles around ten times and end up where we started. Is there an elegant approach that makes ten moves necessary and sufficient?

A little theory

Our first step is to strip the problem down to the studs. We have 16 letters (21 minus the pre-solved five) which we are asked to put back in their original places through a series of two-letter swaps. The fact that Waffle uses words and letters, as well as the grid arrangement itself, is irrelevant to shuffling the puzzle. We just need a generic algorithm to construct permutations of 16 elements which can be undone in ten swaps but no less.

Let’s start by reviewing some terminology. A permutation is a reordering of a sequence; e.g. FCBDAE is a permutation of the sequence ABCDEF (and vice versa). Equivalently, a permutation is a mapping which reorders the sequence, i.e. a bijection from the set of elements of the sequence to itself; the permutation leaving the sequence unchanged is called the identity permutation, which we will denote $\mathrm{id}$. In the previous example we map A to F, B to C, C to B, D to itself, E to A, and F to E.

If we look closely, we’ll notice three subsets permutated independently of one another: A/E/F, B/C, and D. Each of these is called a cycle (or orbit, in group theory parlance). Cycles are usually written as parenthesised ordered lists of their elements—so that in this permutation we have cycles (AEF), (BC), and (D)— and they may be qualified by their size (so (AEF) is a 3-cycle, (BC) a 2-cycle, and (D) a 1-cycle, also called a fixed point). We can better understand why they’re called cycles by representing the permutation as a directed graph instead, where the edges show the mappings between elements:

A well-known result in group theory is that every permutation can be decomposed into disjoint cycles. To do this, pick the first element of the sequence and repeatedly apply the permutation, understood as a mapping (equivalently, follow the arrows around the graph). Since the sequence is finite you will eventually arrive back at the initial element (you cannot arrive at a different repeated element because the mapping is one-to-one); the set of all visited elements constitutes a cycle. Iteratively applying the same method to the next unvisited element in the sequence yields a decomposition of the permutation into disjoint cycles, which is unique up to the starting point of each cycle.

The composition of permutations follows naturally from their definition as mappings: to compose two permutations $\sigma$ and $\tau$, first apply $\tau$ to the sequence and then $\sigma$. This produces a new permutation which may be written $\sigma \circ \tau$ or simply $\sigma \tau$. In our graph representation, we change the incoming edge of each element in the first permutation to point to the element to which it is mapped by the second permutation. For example, composing the cycle (BF) (i.e. swapping B and F) with the previous permutation:

Every permutation $\sigma$ can be inverted straightforwardly (graphically, by reversing the direction of each arrow), producing a new permutation ${\sigma }^{-1}$ such that ${\sigma }^{-1}\circ \sigma =\mathrm{id}$.

Transpositions

We are particularly interested in the effects of composing 2-cycles, or transpositions (what we called swaps earlier), with other permutations. Let’s consider two separate cases: transpositions between two elements of the same cycle and between elements of different cycles. We name the elements of an $N$-cycle $\sigma$ generically as ${\sigma }_i,0\le i<N$, with each element mapped to the next one in the sequence: ${\sigma }_i\to {\sigma }_{(i+1)modN}$.

In the first case, we want to apply a transposition $\left({\sigma }_i{\sigma }_j\right)$ to our permutation. We’ll assign $i$ and $j$ such that $i<j$. This results in two symmetrical changes to our mapping:

• ${\sigma }_{(i-1)modN}\to {\sigma }_i$ becomes ${\sigma }_{(i-1)modN}\to {\sigma }_j$
• ${\sigma }_{j-1}\to {\sigma }_j$ becomes ${\sigma }_{j-1}\to {\sigma }_i$

If we extend the modified mappings we get:

• ${\sigma }_{(i-1)modN}\to {\sigma }_j\to \mathrm{...}\to {\sigma }_0\to \mathrm{...}\to {\sigma }_{(i-1)modN}$
• ${\sigma }_{j-1}\to {\sigma }_i\to \mathrm{...}\to {\sigma }_{j-1}$

These are two new, disjoint cycles, composed of the elements $[{\sigma }_j,{\sigma }_i)$ and $[{\sigma }_i,{\sigma }_j)$, respectively (with indices wrapping around $mod\mathrm{N}$). We can get a better understanding of what’s happening by taking a look at the resulting graph:

Swapping two elements in a cycle, then, produces two new cycles. In particular, swapping two consecutive elements (i.e. $j=i+1modN$) places ${\sigma }_i$ in its own 1-cycle, effectively restoring it to its original place in the sequence (if $N=2$ both elements are restored).

What about two elements in different cycles? With two cycles $\sigma$ and $\tau$ of sizes $N$ and $M$, respectively, we can transpose ${\sigma }_0\leftrightarrow {\tau }_0$ (the particular indices don’t matter here since we can always reindex the cycles). As before, we have two symmetrical changes:

• ${\sigma }_{N-1}\to {\sigma }_0$ becomes ${\sigma }_{N-1}\to {\tau }_0$
• ${\tau }_{M-1}\to {\tau }_0$ becomes ${\tau }_{M-1}\to {\sigma }_0$

This time, however, if we extend the first mapping to get the full cycle, we get:

$${\sigma }_{N-1}\to {\tau }_0\to \mathrm{...}\to {\tau }_{M-1}\to {\sigma }_0\to \mathrm{...}\to {\sigma }_{N-1}$$

That is, transposing two elements from distinct cycles creates a single new cycle by concatenating them. Graphically:

Inverting permutations

Going back to our Waffles, we would like to know how many transpositions (or swaps) are necessary and sufficient to undo (or invert) a permutation. I’m not aware of a standard name for this value, so we’ll call it simply the degree of the permutation, $deg\sigma$. (Implicit here is the assumption that any permutation can be decomposed into a product of transpositions, which is both intuitive and easy to prove).

Once again, let’s start with a single cycle. As we have seen, swapping two consecutive elements of the cycle restores (at least) one of them to its original position. By doing this for every element of the cycle we invert the permutation in exactly $N-1$ transpositions (the last two elements are restored with a single swap). This gives us an upper bound on the degree of an arbitrary permutation of $N$ elements, with $C$ cycles of sizes $N_k,0\le k<C$:

$$deg\sigma \le \sum _k(N_k-1)=\sum _k{N}_k-C=N-C\text{.}$$

Can we do better? Remember that inverting a permutation is the same as transforming it into the identity permutation, which leaves every element untouched and therefore has $N$ 1-cycles. Since every time we transpose two elements we at most add one cycle, we need at least $N-C$ transpositions to invert our permutation, going from $C$ to $N$ cycles. Our upper bound is then also a lower bound: we can place every element back in its place in $N-C$ swaps, but no less.

Clone wars

It would seem we have our answer then: by creating a permutation of our 16 letters with six cycles, we have a puzzle which can be solved in exactly ten moves. Is this enough?

Attentive readers might’ve caught the sleight of hand at the start of my argument. Although in a generic permutation each element is implicitly assumed to be distinct from all others, in Waffle this is not the case: for example, the two Cs in CYCLE are the same for the purpose of solving the puzzle. To see how this affects our solution, try to solve the puzzle below, where the initial permutation has only one cycle:

Unfortunately I couldn't get the interactive examples and game board on this page to work reliably with screen readers to communicate the hint and selection status of each tile. Any advice on how to implement this would be welcome.

According to our reasoning above this puzzle should require four swaps total to solve, but you’ll find you can solve it in only three. Here’s another example, using the words MONAD and OMEGA, to show how this can occur even if no cycle contains duplicate letters:

In this case we would expect to need eight moves: four for each of the 5-cycles, or ten letters minus two cycles. However, it’s possible to solve it in seven moves by taking advantage of the equivalence of the three repeated letters.

To plug this gap in our argument we’ll need to introduce a new concept. We’ll say two permutations $\sigma$ and $\tau$ are equivalent (denoted $\sigma \sim \tau$) if one may be converted into the other through a composition with zero or more transpositions of equivalent elements (in our case, Waffle tiles containing the same letter)². This formalises the intuition that two boards containing the same letters in the same positions are identical, regardless of how we arrived there.

We also define the equivalent degree of $\sigma$, $deg\left[\sigma \right]$, as the lowest number of transpositions required to invert a permutation $\sigma$ or any equivalent permutation³, reflecting the number of moves required to solve the puzzle⁴. We want to understand how the equivalent degree is affected by the structure of the permutation. If $\sigma$ consists of a single $N$-cycle, we have two possibilities:

1. No two elements ${\sigma }_i$ and ${\sigma }_j$ are equivalent. In this case there are no other equivalent permutations so $deg\left[\sigma \right]=deg\sigma =N-1$.

2. There are (at least) two equivalent elements ${\sigma }_i$ and ${\sigma }_j$. As per our earlier result, the equivalent permutation $\left({\sigma }_i{\sigma }_j\right)\sigma$ has two cycles composed of the elements in $[{\sigma }_j,{\sigma }_i)$ and $[{\sigma }_i,{\sigma }_j)$. We can decompose them further if and only if there exist indices $k,l$ with $k,l\in [j,i)$ or $k,l\in [i,j)$ (that is, “nested” within the wider interval) such that ${\sigma }_k\sim {\sigma }_l$, and so on recursively until no resulting cycle has two equivalent elements. If the longest such subsequence of nested equivalent pairs, $({\sigma }_i,{\sigma }_k,...,{\sigma }_l,{\sigma }_j)$, is $E\left(\sigma \right)$, the number of cycles in this decomposition is then $\frac{1}{2}\left|E\left(\sigma \right)\right|+1$⁵.

If $\sigma$ has more than one cycle, we also have to consider the transposition of equivalent elements in different cycles. As we have seen, transposing two such elements concatenates their respective cycles, creating a new cycle (say $\sigma \text{'}$) which falls under the second case above. This cycle may then be decomposed into more than the two initial ones if $\left|E\right(\sigma \text{'}\left)\right|>2$.

Back in the kitchen

Where does this leave us, in our quest to build permutations of a specific equivalent degree? The analysis from the last section gives us two requirements:

1. A cycle cannot contain equivalent elements, so that it falls into case 1 above.
2. Joining any two cycles by transposing two of their elements can produce at most two nested equivalent pairs (resulting in three equivalent cycles and a decrease of the equivalent degree by one).

The first condition is straightforward enough. The easiest way to deterministically guarantee the second condition is to enforce a unique ordering of elements across all cycles (proving this works is left as an exercise to the reader). This rules out some “harmless” inversions and so does not completely cover the space of valid permutations, but it does not affect gameplay and it’s a small price to pay for a fast and simple algorithm:

1. Initialise each cycle to an empty list.
2. Shuffle the unique letters of the puzzle to obtain an ordering.
3. Sort the (non-fixed) tiles according to this ordering.
4. For each tile, append it to either the next uninitialised cycle, if there is one, or otherwise to a random cycle which does not already contain a tile with the same letter.
5. Permutate the tiles according to the resulting cycles.

This is the logic I have implemented in my Waffle clone, which you can try out below:

Conclusion

I found this to be a great example of a situation where you can easily explain both the problem and its solution, but why the solution works and how to get there turns out to be more intricate than one might expect. The algorithm can be extended to manipulate the difficulty of solving the puzzle by requiring a certain initial balance of solved and hint squares, or by controlling the size distribution of the cycles. Understanding the permutation structure as we explored it here is also helpful to implement an optimal (automated) solver.

Throughout the discussion I assumed we had already selected the words to shuffle in some way. In my implementation I used a very naive approach with no optimisation whatsoever which, despite producing new games essentially instantly for word lists in the thousands of entries, presents some drawbacks (most notably, it’s almost impossible for some words to be present in the first row). This is an interesting problem to explore on its own, which I will leave for a future post.

I want to emphasise that my clone is purely a for-fun project, with none of the care and charming human touches on which James works so hard. If you appreciated this write-up I encourage you to support him by playing the real version!