The Weaver Android app $\rightarrow$ cute combinatorics problem

Question

There's an Android puzzle app called "The Weaver". My question is why every level seems to be solvable in far fewer moves than one might naively think.

Here's a link for people who want to play along on their Android devices, but this is not necessary to understand the question. (NB I am nothing to do with promoting this game in any way; I am an end user who just got interested in the mathematics behind the game).

It's very easy to explain the objective of this puzzle game. A level looks like this when you start it:

and it looks like this when you've finished it:

The ribbons "flow" from top to bottom and you can twist or untwist two ribbons by tapping on where they meet. You can't change the order of the ribbons going "in" (from the top) or their colours. The object is to twist the ribbons around within the rectangular grid so that the "output" of the grid matches the small coloured squares. For example, in the game above, initially only one output square is matched -- the green square which is enabling a green ribbon to "escape" from the rectangular grid. All other squares don't match and so some ribbon-twisting is needed. A move on a level consists of twisting or untwisting two ribbons (by tapping on them). It's very cute.

There is also a "star" system, and to get 3 stars in a level you must solve it using the minimum number of "twists". As you can see I've done a very bad job at solving level 2.4; I've got no stars at all. There are solutions to this level with fewer twists -- in fact this is obvious, because in my solution here the bottom "switch" is switched but it doesn't need to be -- those two orange ribbons could just pass over each other.

The question.

I worked through the levels of this game, and I was quite surprised to find that even on big boards (the biggest is 6x6) one always seemed to be able to solve them in far fewer moves than I expected. Although the the game's board size never gets bigger than $6\times 6$ and there are also only 6 colours in the app, one can of course just dream about arbitrarily large boards involving arbitrarily many colours.

Conjecture On an $a$ by $b$ board, if the level is solvable at all, then it is solvable in at most $a+b-1$ moves (i.e. with at most $a+b-1$ "untwists").

In particular I am conjecturing that the largest number of twists you need to make is $O(a+b)$ rather then $O(ab)$.

Here is what I know about this conjecture.

Lemma The conjecture is true if $a=1$.

Proof: trivial (there are only $b=a+b-1$ switches on the board).

Lemma the conjecture is true if $a=b=2$

Proof: the only counterexample would be a board for which the only solution would be with all four switches switched. But unswitching the top and the bottom switch leads to the same order of ribbon outputs.

Lemma The conjecture is true if $ab\leq 20$.

Proof: brute force computer search.

Note that in this latter case I will allow an arbitrary number of colours (not just 6 as in the app).

Lemma The conjecture is true for all 150 levels that come with the game.

Proof: brute force check.

Lemma For given $a,b\geq1$ there exists a level whose only solution involves $a+b-1$ twists (and in particular my conjecture is best possible).

Proof: One checks that the level with $a+b$ distinct input ribbons and which is solved by switching the $a+b-1$ switches comprising the top right and bottom right sides of the grid of switches, has this property (NB the check is rather easier to do once you have played a few levels and got the hang of the combinatorics).

I think that's everything I know. Can anyone finish the job by proving my conjecture?

---

[Added two days later] Here is my interpretation of some discussions (now deleted) with Calum Gilhooley -- a group-theoretic interpretation of the conjecture (but it's a slightly strange group-theoretic question).

We fix positive integers $a$ and $b$, and define a set $S=\{r_1,r_2,\ldots,r_a,s_1,s_2,\ldots,s_b\}$ of $a+b$ symbols (thought of as the ribbons). Each "switch" can be thought of as a transposition, and it's important to note that with the model I'm about to describe, the initial state of the switch is that the ribbons cross so the transposition is actually a transposition (i.e. it can be switched off rather than on). The following picture shows why the convention is sensible -- when all the switches are switched we have something that looks like the identity as you can see from the picture below.

We read the transpositions from top to bottom in the picture; if the $r_i$ and $s_j$ are also numbered from top to bottom then the first transposition is $(r_1\ s_1)$, the next two (which commute so can be made in either order) are $(r_1\ s_2)$ and $(r_2\ s_1)$ and so on; at the $n$th step we consider $(r_i\ s_j)$ for $i+j=n+1$ and this goes down to the final transposition $(r_a\ s_b)$. Multiplying all of these $ab$ transpositions together gives us an element $X=(r_1\ s_1)(r_1\ s_2)(r_2\ s_1)\cdots(r_a\ s_b)$. This is the initial state of the board.

Now for $S$ a subset of $\{1,2,\ldots,a\}\times\{1,2,\ldots,b\}$ we can consider the element $X_S$ obtained by taking the product representation of $X$ and then removing the transpositions $(r_i\ s_j)$ for $(i,j)\in S$ (and multiplying those that we didn't remove together in the same order as we did to get $X$).

Reformulation of the question Is it true that for $S\subseteq\{1,2,,\ldots,a\}\times\{1,2,\ldots,b\}$ the permutation $X_S$ is equal to $X_T$ for some $T$ of size at most $a+b-1$?

Here is a special case: is it true that the identity can be written as $X_T$ for some $T$ of size at most $a+b-1$? That's probably a relatively easy question. It's true for $a=b$, that's not hard to check.

Answer 1

This can be solved by the following greedy strategy (where we assume each ribbon has a unique color and hence a unique target, as all cases may be reduced to this one). The main body of the post proves it solves things in at most $n+m-1$ moves. The addendum proves that it is optimal:

Fill the grid from top to bottom (i.e. starting at the topmost cell, moving to the two cells below it, then the three in the next row, and so on) and make a twist* only when it will cause a ribbon to head directly for its output.

This works because, as we go down making moves from top to bottom, we will know that the outgoing path of any twist we make will be free of twists - that is, going top to bottom ensures that if we send a ribbon straight towards its output, it will not be diverted along the way, unless we make an additional twist later. However, we will never make an additional twist in the path of a ribbon heading towards its target in our strategy - that is, if we have a ribbon of color $A$ heading towards the target of color $A$ intersection with a ribbon of color $B$, then making the twist will send the ribbon of color $B$ to the target of color $A$ and the ribbon of color $A$ to the target of another color - which means our strategy would not make a twist. This situation is illustrated as follows:

where the dotted lines indicate what would happen if we did make a twist. This would be stupid, so we never do things like that. (The figure also illustrates the implicit hypothesis that there is a section free of twists, which we never violate so long as we move top down in our twisting). Thus, we use at most one twist per ribbon.

Knowing that if we send a ribbon towards its target, it will reach it, we just need to show that we will, at some point, send each ribbon towards its target. We can do this by induction. In particular, suppose we have an output $O$ on the left-bottom side (noting that symmetry carries the argument to the right-bottom side) such that all the outputs above it (i.e. to the left and up of $O$) will be connected to their proper inputs by using my strategy. One may consider the "row" of intersections above the output $O$. If the corresponding ribbon starts in this row, then it was always headed towards its proper output and we will never twist it in our strategy. Otherwise, consider that, if we think of the game as a graph with vertices at the intersections and edges where the ribbons are (with additional edges & vertices for where ribbons enter and exit), then we can note that removing the row above $O$ splits the graph into two connected segments - one "above" the row (i.e. the points from where $O$ could be reached by a descending ribbon) and one below. The ribbon going to $O$ must start in the segment above the row, since otherwise it could not possibly reach $O$ and the puzzle would unsolvable. However, it must end in the segment below the row because the only outputs in the upper segment would be those above $O$ - which would be connected to their appropriate ribbons and hence not to the one destined for $O$. Thus, the ribbon must head for an output not in the upper section - but to do this, it must at some point enter the row above $O$, at which point it will be diverted towards $O$ and therefore find its solution. To illustrate this, we have another pretty picture: where we can see that, no matter which possible input we choose to put the purple ribbon belonging to $O$ in, it must cross the row of $O$ since all the exits in the upper section are already filled. When it crosses the row of $O$, we divert it.

Thus, this strategy always works and uses at most one twist per ribbon. If we pause to consider the state after (at most) $n+m-1$ twists, all but one ribbon will be connected to its output. However, since all the other outputs would be taken, that last ribbon must too be connected. Thus, this strategy works on all puzzles and takes no more than $n+m-1$ moves.

Here's a picture of it applied to the puzzle you posted, where the numbers indicate what order the moves take place in. Since the colors are non-unique, I used the rule that I'd make a twist only if it would send a ribbon directly for its output and, given the rows above, no other ribbons could possibly go to that output:

*I think you may be calling what I call a "twist" an "untwists". I found that confusing, so I changed it.

---

Addendum:

Based on the insights in Calum Gilhooley's comments and answers, one can in fact prove that the above strategy is optimal. In particular, let $\pi$ be a permutation on the ribbons such that if $r$ is a ribbon, $\pi(r)$ is the ribbon that initially passes to the output that $r$ is supposed to. As is further explicated in Calum's answer, if we pass through the grid from top to bottom and write down the transpositions $T_i=(r_1 r_2)$ if the $i^{th}$ twist we encounter is the twisting of the ribbons $r_1$ and $r_2$, then $$\text{id} =T_nT_{n-1}\ldots T_2T_1\pi$$ since, for each twist, we essentially are swapping the identity of $r_1$ and $r_2$ for all further twists, and the idea is that at the end, we have undone the swapped identities at the start. It is a standard fact in group theory that a $c$-cycle is a product of at least $c-1$ transpositions, and it is not too difficult to additionally show that if $\pi$ is a permutation on $R$ elements with $C$ cycles, then it is the product of at least $R-C$ transpositions. In particular, we get the following characterization:

Any starting position can be solved in $R-C$ moves and no fewer.

To prove the optimality of my strategy, one simply notes that ribbons $r_1$ and $r_2$ will only interact if they are in the same cycle of $\pi$. In particular, the following truth is never changed by my strategy:

Each ribbon is, at all times, heading towards an output corresponding to a ribbon in the same cycle.

This is because if $r_1$ and $r_2$ are twisted in a state satisfying the above, where we send $r_1$ towards its target, then $r_2$ was, beforehand, pointing at the target of $r_1$ and by the above hypothesis, it follows that $r_1$ and $r_2$ are of the same cycle. Moreover, if $r_1$ was initially headed for the output for $r_3$, then $r_1$ and $r_3$ are in the same cycle - and thus, by transitivity, $r_2$ and $r_3$ are in the same cycle, and hence $r_2$ will be afterwards headed for the target of a ribbon in its cycle ($r_3$).

Then, given this and the fact that the strategy functions and assigns no more than one twist each ribbon, it is clear that it solves a cycle in $C-1$ steps. Thus it solves the game in $R-C$ steps and is thus optimal. The only question remaining is how to optimally assign inputs to outputs when the colors are non-distinct.

Answer 2

Let $m$ and $n$ be positive integers. Denote the set $\{0, 1, \ldots, m - 1\}$ by $M.$ Let $p = m + n - 1,$ and denote the set $\{m, m + 1, \ldots, p\}$ by $N$. Let $\pi$ be any permutation of the set $P = M \cup N = \{0, 1, \ldots, p\}$ that satisfies the conditions: \begin{align*} i < m & \implies \pi(i) \leqslant i \text{ or } \pi(i) \geqslant m, \\ i \geqslant m & \implies \pi(i) \geqslant i \text{ or } \pi(i) < m. \end{align*}

Create a $(2m + 1) \times (2n + 1)$ table, with columns numbered from left to right, and rows numbered from top to bottom, both starting at $0$. Its top row has the number $h$ written in position $2h + 1$ ($h = 0, 1, \ldots, m - 1$). Its right-hand column has the number $k$ written in position $2k - 2m + 1$ ($k = m, m + 1, \ldots, p$). The remaining $2m \times 2n$ subtable is to be regarded as an $m \times n$ table of $2 \times 2$ tables, called cells, numbered from $0$ to $m - 1$ horizontally from left to right, and from $m$ to $p$ vertically from top to bottom (as already labelled by the numbers written in the top row and rightmost column of the $(2m + 1) \times (2n + 1)$ table).

$$ \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline & & & & 2 \\ & & & & \\ \hline & & & & 3 \\ & & & & \\ \hline & & & & 4 \\ & & & & \\ \hline \end{array} \\ \text{Layout for } m = 2, n = 3\ (p = 4). $$

The set $Q = M \times N$ is partially ordered by the relation: $$ (h, k) \leqslant (h', k') \iff h \leqslant h' \text{ and } k \geqslant k'. $$ An ideal (downward-closed subset) of this partially ordered set corresponds to a zig-zag line drawn through the $2m \times 2n$ subtable, from its top left-hand corner to its bottom right-hand corner, enclosing all the cells below and to the left of it. Such a line can be represented uniquely by a sequence of $m$ rightward-pointing arrows and $n$ downward-pointing arrows, in an arbitrary order; thus $Q$ has $(m + n)!/(m!n!)$ ideals. The empty ideal $\emptyset$ is represented by the sequence $\downarrow\cdots\downarrow\rightarrow\cdots\rightarrow$, and $Q$ itself by the sequence $\rightarrow\cdots\rightarrow\downarrow\cdots\downarrow$. In a Hasse diagram of the ideals of $Q$, an ideal is covered by all the ideals whose sequences are obtained from its sequence by replacing a subsequence $\downarrow\rightarrow$ with $\rightarrow\downarrow.$ These four arrows represent the edges of a single $2 \times 2$ cell.

We define a nondeterministic computational procedure - in effect a kind of game - as follows.

Computation starts with an (almost) empty table. The state of the computation, at any time, consists of a table whose filled-in cells constitute an ideal of $Q.$ Computation terminates when all of the $m \times n$ cells have been filled in.

We may move at any time to a state whose ideal covers the previous one. The two ideals differ by a single cell, whose location in the $m \times n$ table of cells is denoted in what follows by $(h, k).$ The empty ideal is covered only by the ideal $\{(0, p)\},$ therefore initially $h = 0$ and $k = p.$

Computation proceeds in such a way that every cell $(h, k)$ eventually has a number written in its lower right corner, denoted by $i$, and a number written in its upper left corner, denoted by $j:$ $$ \begin{array}{|ccc|c|} \hline & h & & \\ \hline & \vdots & & \\ \cdots & \boxed{\begin{array}{cc} j & \\ & i \end{array}} & \cdots & k \\ & \vdots & & \\ \hline \end{array} \\ \text{A partially filled cell.} $$

When this happens, we always have: \begin{gather*} h \leqslant i \leqslant k, \\ h \leqslant j \leqslant k. \end{gather*} This is because the two "ribbons" that pass through cell $(h, k)$ have originated in locations $i$ and $j$ at the top or rightmost edge of the table. The purpose of the computation is to trace these two ribbons, by working backward, one step at a time, to the two cells they have most recently passed through. The algorithm maintains these inequality relations between $h, i, j, k,$ as an invariant condition; and in fact, they determine pretty much everything it does. The given inequality conditions on the permutation $\pi$ are sufficient to ensure that the computation can always proceed.

A second invariant condition of the algorithm is that $\pi$ is always equal to the composite of the sequence of transpositions generated so far (initially empty) followed by a permutation $\theta$ that permutes only those elements of $P$ that are arranged, in some sequence, along that part of the upper right edge of the "zig-zag" line (representing the current ideal of processed cells) that has not yet reached the top or rightmost edge of the array. (This convoluted description will become clearer when we follow the record of an actual computation.) Thus: $$ \pi = \tau_1 \cdots \tau_q\theta, $$ where concatenation of functions denotes the opposite of the composition operator, $\circ$ (i.e. $\varphi\psi = \psi\circ\varphi$). At the end of the computation, $\theta$ is the identity map on $P$, and $\pi$ is therefore equal to the composite of all the transpositions generated by the algorithm, in the sequence of their generation. (The algorithm is nondeterministic, therefore the sequence is indeterminate, reflecting the fact that disjoint transpositions commute.) At the beginning of the computation, of course, $\theta = \pi.$

This discussion has brought us to the matter of the initial "almost empty" state of the game. Just enough numbers are filled in to ensure a sufficient supply of values of $i$ and $j$ to keep the computation going to the end. The initial configuration is determined by the permutation $\pi,$ as follows.

For $h = 0, 1, \ldots, m - 1,$ write the number $\pi^{-1}(h)$ into the lower right corner of the cell in position $(h, p)$ of the $m \times n$ array of cells. For $k = m, m + 1, \ldots, p,$ write the number $\pi^{-1}(k)$ into the upper left corner of the cell in position $(0, k).$

$$ \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 1 & & & & 2 \\ & & & & \\ \hline 0 & & & & 3 \\ & & & & \\ \hline 3 & & & & 4 \\ & 2 & & 4 & \\ \hline \end{array} \\ \text{Layout for the permutation } (0\,3\,4\,1\,2). $$

If programming this on a computer, one might as well represent the 'blank' value of the unfilled locations in the remaining cells by the unused integer value $m + n.$ Note, however, that the upper right corners of cells are not to be filled with numbers, but rather with transpositions or identity maps, or representations of these. Lower left corners of cells are not used at all; they do not exist, mathematically speaking; but it is hard to devise a readable pencil-and-paper representation of the computation in which no space is wasted. (Pen-and-paper, rather, because there is never any need to erase values that have been written.) I did design a sort of diamond-shaped graph paper for this purpose, but it was very hard to see what was going on, so I reverted to using normal-looking tables.

In considering the processing of a cell $(h, k),$ containing information $(i, j),$ we will ultimately need to distinguish all possible combinations of the 6 exceptional cases of equality in the following non-strict inequalities: \begin{align*} h & \leqslant m - 1, \\ k & \geqslant m, \\ h & \leqslant i \leqslant k, \\ h & \leqslant j \leqslant k. \end{align*} Without some guiding intuition, this is obviously liable to become complicated, so it is time to look at a particular example. We have already set up the initial position for the case $m = 2$, $n = 3$, $\pi = (0\,3\,4\,1\,2),$ so let us see how it develops.

In these diagrams: a red bullet denotes a compulsory transposition; a black bullet denotes a place where it is impossible to create a transposition; and a green bullet denotes a voluntary decision not to transpose, with the (apparently successful) intention of minimising the resulting total number of transpositions. \begin{gather*} \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 1 & & & & 2 \\ & & & & \\ \hline 0 & & & & 3 \\ & 2 & & & \\ \hline 3 & \color{green}{\bullet} & 3 & & 4 \\ & 2 & & 4 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 1 & & & & 2 \\ & & & & \\ \hline 0 & & & & 3 \\ & 2 & & 3 & \\ \hline 3 & \color{green}{\bullet} & 3 & \color{red}{\bullet} & \color{red}{4} \\ & 2 & & 4 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & \color{red}{0} & & 1 & \\ \hline \hline 1 & & & & 2 \\ & 0 & & & \\ \hline 0 & \color{red}{\bullet} & 2 & & 3 \\ & 2 & & 3 & \\ \hline 3 & \color{green}{\bullet} & 3 & \color{red}{\bullet} & \color{red}{4} \\ & 2 & & 4 & \\ \hline \end{array} \\ \begin{array}{|cc|cc||c|} \hline & \color{red}{0} & & 1 & \\ \hline \hline 1 & & & & 2 \\ & 0 & & 2 & \\ \hline 0 & \color{red}{\bullet} & 2 & \color{red}{\bullet} & \color{red}{3} \\ & 2 & & 3 & \\ \hline 3 & \color{green}{\bullet} & 3 & \color{red}{\bullet} & \color{red}{4} \\ & 2 & & 4 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & \color{red}{0} & & 1 & \\ \hline \hline 1 & \bullet & 1 & & 2 \\ & 0 & & 2 & \\ \hline 0 & \color{red}{\bullet} & 2 & \color{red}{\bullet} & \color{red}{3} \\ & 2 & & 3 & \\ \hline 3 & \color{green}{\bullet} & 3 & \color{red}{\bullet} & \color{red}{4} \\ & 2 & & 4 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & \color{red}{0} & & \color{red}{1} & \\ \hline \hline 1 & \bullet & 1 & \color{red}{\bullet} & \color{red}{2} \\ & 0 & & 2 & \\ \hline 0 & \color{red}{\bullet} & 2 & \color{red}{\bullet} & \color{red}{3} \\ & 2 & & 3 & \\ \hline 3 & \color{green}{\bullet} & 3 & \color{red}{\bullet} & \color{red}{4} \\ & 2 & & 4 & \\ \hline \end{array} \end{gather*}

The following table provides more information, especially the shape of the "zig-zag line", which ideally I would have liked to draw in blue as part of the above diagrams. The "unsorted" column shows the list of numbers that were described above, rather unhelpfully, as "those elements of $P$ that are arranged, in some sequence, along that part of the upper right edge of the zig-zag line (representing the current ideal of processed cells) that has not yet reached the top or rightmost edge of the array." $$ \begin{array}{|c|c|cccc|c|c|c|} \hline \text{ideal} & \text{unsorted} & h & i & j & k & \text{action} & \text{reason} & \text{factor} \\ \hline \hline \downarrow\downarrow\downarrow\rightarrow\rightarrow & 01234 & 0 & 2 & 3 & 4 & \text{refrained} & \text{trying to minimise} & \text{id} \\ \hline \downarrow\downarrow\rightarrow\downarrow\rightarrow & 01234 & 1 & 4 & 3 & 4 & \text{obliged} & i = k = 4 & \color{red}{(3\,4)} \\ \hline \downarrow\downarrow\rightarrow\rightarrow\downarrow & 0123 & 0 & 2 & 0 & 3 & \text{obliged} & j = h = 0 & \color{red}{(0\,2)} \\ \hline \downarrow\rightarrow\downarrow\rightarrow\downarrow & 0123 & 1 & 3 & 2 & 3 & \text{obliged} & i = k = 3 & \color{red}{(2\,3)} \\ \hline \downarrow\rightarrow\rightarrow\downarrow\downarrow & 012 & 0 & 0 & 1 & 2 & \text{forbidden} & i = h = 0 & \text{id} \\ \hline \rightarrow\downarrow\rightarrow\downarrow\downarrow & 12 & 1 & 2 & 1 & 2 & \text{obliged} & i = k = 2; j = h = 1 & \color{red}{(1\,2)} \\ \hline \rightarrow\rightarrow\downarrow\downarrow\downarrow & \text{none} & \bot & \bot & \bot & \bot & \text{finished} & \text{n/a} & \text{n/a} \\ \hline \end{array} $$

The conclusion is: $(0\,3\,4\,1\,2) = (3\,4)(0\,2)(2\,3)(1\,2),$ which is correct.

In the general case, what is at least intuitively clear is that (a) one can only be compelled to introduce a transposition once for each of the $m + n$ numbers in the set $P$, and (b) if one is compelled to transpose in the top right corner cell $(m - 1, m),$ then one cannot previously have been compelled to transpose for either $m - 1$ or $m$; therefore, at most $m + n - 1$ transpositions are needed.

Meelo's example

In Meelo's answer, there is an image of an initial game position, with numbers $1$ to $5$ written over it, to show where Meelo's strategy places the $5$ 'twists' needed, and the order in which they are placed.

Although I have some difficulty in understanding Meelo's description of his strategy (just as people seem to be having some difficulty in understanding this description of my strategy!), it seems increasingly clear that our strategies are essentially identical, differing only in how they are described. (That's a good thing - the more different ways the same idea is described, the more likely it is that a reader will find some description that makes sense to them.)

To help in showing the isomorphism of our two approaches, I have prepared a series of four snapshots of my algorithm in action, on the same initial game position, producing $5$ twists in the same places, and in the same order.

It may help if you visualise the tables below as being rotated through a clockwise angle of $\frac{3\pi}{4}$, and superimposed on the screenshot in Meelo's illustration, with the numerical column labels $0$ and $1$, and row labels $2$ to $7$, superimposed on the eight little coloured squares on the screen, and serving also to label the eight ribbons entering the opposite edges of the rectangular game grid.

Meelo and I agree that the permutation representing the mapping of ribbons to little coloured squares is then: $(0\,6\,4\,3\,2)(1\,5).$ This is the inverse of the permutation $\pi = (0\,2\,3\,4\,6)(1\,5)$ used to set up the initial configuration for my algorithm, which is shown in the first of the four tables below.

The last of the four tables, of course, shows the final configuration, and it is clear that the red bullets, representing transpositions, align with the numbers $1$ to $5$ in Meelo's illustration.

It is clear from his positioning of the numbers $2$ and $3$, in particular, that Meelo's strategy processes the intersection positions of the ribbons from left to right at each level. Accordingly, I have processed the cells of my tables in order from bottom right to top left, after each move outward by one more level from the bottom left hand corner of the table (which corresponds to moving downward from the top of the game grid in the screenshot).

In between the initial and final configurations, I have shown two successive snapshots, taken respectively before and after the processing of the cell in location $(1, 4)$ of the table. In each entry in the 'ideal' column, I have inserted a box to show which cell is currently being processed: after cell $(1, 4)$ has been processed, the algorithm moves on to process cell $(0, 3)$.

\begin{gather*} \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 0 & & & & 2 \\ & & & & \\ \hline 2 & & & & 3 \\ & & & & \\ \hline 3 & & & & 4 \\ & & & & \\ \hline 1 & & & & 5 \\ & & & & \\ \hline 4 & & & & 6 \\ & & & & \\ \hline 7 & & \phantom{7} & & 7 \\ & 6 & & 5 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 0 & & & & 2 \\ & & & & \\ \hline 2 & & & & 3 \\ & 3 & & & \\ \hline 3 & \color{red}{\bullet} & 4 & & \color{red}{4} \\ & 4 & & 1 & \\ \hline 1 & \color{green}{\bullet} & 1 & \color{red}{\bullet} & \color{red}{5} \\ & 4 & & 5 & \\ \hline 4 & \color{red}{\bullet} & 6 & \bullet & \color{red}{6} \\ & 6 & & 5 & \\ \hline 7 & \bullet & 7 & \bullet & 7 \\ & 6 & & 5 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 0 & & & & 2 \\ & & & & \\ \hline 2 & & & & 3 \\ & 3 & & 1 & \\ \hline 3 & \color{red}{\bullet} & 4 & \bullet & \color{red}{4} \\ & 4 & & 1 & \\ \hline 1 & \color{green}{\bullet} & 1 & \color{red}{\bullet} & \color{red}{5} \\ & 4 & & 5 & \\ \hline 4 & \color{red}{\bullet} & 6 & \bullet & \color{red}{6} \\ & 6 & & 5 & \\ \hline 7 & \bullet & 7 & \bullet & 7 \\ & 6 & & 5 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & \color{red}{0} & & 1 & \\ \hline \hline 0 & \color{red}{\bullet} & 2 & \bullet & \color{red}{2} \\ & 2 & & 1 & \\ \hline 2 & \color{red}{\bullet} & 3 & \bullet & \color{red}{3} \\ & 3 & & 1 & \\ \hline 3 & \color{red}{\bullet} & 4 & \bullet & \color{red}{4} \\ & 4 & & 1 & \\ \hline 1 & \color{green}{\bullet} & 1 & \color{red}{\bullet} & \color{red}{5} \\ & 4 & & 5 & \\ \hline 4 & \color{red}{\bullet} & 6 & \bullet & \color{red}{6} \\ & 6 & & 5 & \\ \hline 7 & \bullet & 7 & \bullet & 7 \\ & 6 & & 5 & \\ \hline \end{array} \end{gather*}

$$ \begin{array}{|c|c|cccc|c|c|c|} \hline \text{ideal} & \text{unsorted} & h & i & j & k & \text{action} & \text{reason} & \text{factor} \\ \hline \hline \downarrow\downarrow\downarrow\downarrow\downarrow \boxed{\downarrow\rightarrow} \rightarrow & 01234567 & 0 & 6 & 7 & 7 & \text{forbidden} & j = k = 7 & \text{id} \\ \hline \downarrow\downarrow\rightarrow \boxed{\downarrow\rightarrow} \downarrow\downarrow\downarrow & 01234 & 1 & 1 & 4 & 4 & \text{forbidden} & i = h = 1;\ j = k = 4 & \text{id} \\ \hline \downarrow \boxed{\downarrow\rightarrow} \rightarrow\downarrow\downarrow\downarrow\downarrow & 0123 & 0 & 3 & 2 & 3 & \text{obliged} & i = k = 3 & (2\,3) \\ \hline \rightarrow\rightarrow \downarrow\downarrow\downarrow\downarrow\downarrow\downarrow & \text{none} & \bot & \bot & \bot & \bot & \text{finished} & \text{n/a} & \text{n/a} \\ \hline \end{array} \ \, \ \, $$

The algorithm correctly concludes that $\pi = (4\,6)(1\,5)(3\,4)(2\,3)(0\,2).$