Permutation puzzles

This post builds further on God's number.

Yesterday, I put together a small tool to explore permutation groups and how they are structured with respect to generating the entire group from some base elements. Here are some thoughts and insights!

Symmetry

First, I tried a series of simple group elements; swapping two adjacent numbers. For example, 1 0 2 3, 0 2 1 3 and 0 1 3 2. These generate $S_4$ in its entirety. God's number for this puzzle is 6, and, perhaps unsurprisingly, the single "hardest" element to reach is 3 2 1 0. This element is the only one that requires the full 6 moves. In general, it seems that this type of choice of base elements in $S_n$ leads to God's number being $g = \tfrac12 n(n - 1)$ elements. Curiously, the amount of elements that need $i$ moves to be solved seems to be equal to the amount of elements that need $g - i$. There is always one element the hardest to get, which is the identity written backwards. Quite satisfyingly, solving the group to the identity is just as hard as solving it to the reverse identity; the puzzle is completely symmetric. Initially, I thought; well, that kind of makes sense; the base elements we chose were entirely symmetric, so it's not surprising that the puzzle also is. But, as it turns out, that's not quite right. If we add the one element swapping the first and last number (in the example for $S_4$, 3 1 2 0) then the solution spaces are no longer symmetric, with elements needing a number of moves closer to God's number on average.

Perhaps the reason the specific choice of base elements leads to a symmetric puzzle is due to how the solutions are composed. The optimal solution turns out to be moving the numbers in the permutation from out- to inwards; for example, this is the steps we'd use to solve 3 2 1 0:

• 3 2 1 0
• 2 3 1 0
• 2 1 3 0
• 2 1 0 3 (now the puzzle is essentially reduced to the one in $S_3$)
• 1 2 0 3
• 1 0 2 3 (reduced to $S_2$)
• 0 1 2 3

It doesn't matter which side we are completing; the goal is to reduce the puzzle to a simpler one. Once the 3 is in place, the move 0 1 3 2 becomes usless; it doesn't do anything that the other permutations can't do in the same (or fewer) number of moves. This also explains that God's numbers for these types of puzzle groups are triangle numbers; we can show this with induction.

Distance

We can define a "distance" $d: G^2\to\mathbb{N}$ between two elements in a puzzle as the least amount of moves needed to get from one to the other. Since we consider powers of each move as moves themselves, this means $d(a, b) = d(b, a)$. This must be true, since if $q$ represents a series of moves $m_1, m_2, \dots, m_i$, then $q^{-1} = m_i^{-1} \dots m_1^{-1}$ also represents a series of moves, and an equally long one at that. That means if $a \cdot q = b$ then $b \cdot q^{-1} = a$, proving that $d(a, b) = d(b, a)$.

We also know that $d(a, b) \leq g$ (where $g$ is God's number). This must be true since, if $a \cdot m_1 \dots m_i = b$, then $b^{-1} a m_1 \dots m_i = 1$. This shows that $i\leq g$ and therefore $d(a, b) \leq g$ for any $a,b\in G$.

The amount of moves needed to "solve" a specific state $a$ is then exactly $d(a, 1)$. In general, $d(a, b) = d(c\cdot a, c\cdot b)$ since if $q$ is a solution to get from $a$ to $b$, then $a\cdot q = b$, and therefore $c\cdot a\cdot q = c\cdot b$. This is not (necessarily) true for right multiplication, i.e. $d(a, b)$ is not always equal to $d(a \cdot c, b \cdot c)$.

Lastly, like all well-behaving metric spaces, we find the triangle inequality

$$d(a, b) + d(b, c) \geq d(a, c)$$

This is true since, if $a \cdot q = b$ and $b \cdot r = c$, then definitely $a\cdot q\cdot r = c$. The shortest distance to get from $a$ to $c$ is therefore at most as long as $q\cdot r$, and potentially shorter.

With this notion of distance, we can define a sort of "absolute value" to be the distance to the solved state. That is, $|a| := d(a, 1)$. The triangle inequality then shows that $|a| + |b| \geq |b^{-1}\cdot a|$.

Loops

An interesting thing happens at some point down the line of generating solutions; a single state $a$ might have multiple distinct solutions. In formula, it means there are two different moves $m$ and $k$ such that both $|a\cdot m| < |a|$ and simultaneously $|a\cdot k| < |a|$. For the Rubik's cube, this does not happen until $|a| = 5$. Specifically, we find:

$$(L^{-1}\cdot U^{-1}\cdot L^2\cdot F^{-1}\cdot D^{-1}) (L\cdot D\cdot L^2\cdot F\cdot U) = 1$$

After the first 5 moves, we can actually choose whether we do $D$ or $L$, and both solve the cube optimally. This type of product can actually be quite useful in solving some groups optimally, since we can first find a solution of any length (this is not particularly hard) and then find sub-prodocts in the solution that resemble part of the product above. If a series of 6 moves coincides with above, then we can remove them in favor of the four moves that are equivalent. I'm not sure if that is a viable strategy, though; for a Rubik's cube, I imagine you'd need a lot of these types of products to reduce a long solution down to an optimal one.