A Guide to the Number Rotation Puzzle

Question

This is an extension of What is the strategy to solve Simon Tatham's Twiddle? in that it explicitly goes beyond the default gamemodes of Twiddle

---

The Number Rotation Puzzle (NRP) is a combination puzzle in which the goal is to rearrange a scrambled rectangular grid of numbers back into order via moves that consist of rotating square blocks of numbers of fixed size. For instance, here is the classical instance of the NRP, which is played on a $3 \times 3$ and uses $2 \times 2$ rotating blocks:

The board starts as some permutation of the numbers from 1 to 9. Here, I am rotating the upper-left block counter-clockwise.

After the first move, I rotate the bottom-right block clockwise.

These two moves solve the puzzle, because the nine numbers are now in increasing book-order.

Larger variations exist. For example, here is a $16 \times 25$ board with $9 \times 9$ rotating blocks:

(A sample move's rotation is shown in progress)

What is the strategy for solving the NRP? Specifically:

1. Over all possible board sizes and rotating block sizes, what are all possible initial configurations that are solvable?
2. What is the solving strategy to solve such boards?

---

Note: Because of the answer character limit, my self-answer had to be split into two. These answers may not be in order. If so, try sorting by oldest.

Answer 1

Part III: Spiral and Cycle

Well, yay! Now we have a solid 3-cycle for all $n \geq 4$. Smaller $n$ values are probably special cases. So we're gonna call $n \geq 4$ the general case. Have we basically solved the general case? No, because we only have a specific 3-cycle algorithm, i.e. we have an algorithm that can only cycle three numbers in these three set locations. I want to be able to choose any three numbers I want and cycle them. What do I do now?

The idea is that I'm going to use my specific 3-cycle to create my general 3-cycle algorithm. Here's basically how it's going to work:

1. Choose 3 numbers you want to cycle.
2. Move them to the 3-cycle squares (the three squares that you know can be 3-cycled). It's ok if other numbers' positions are ruined.
3. Execute the 3-cycle.
4. Undo the moves in step 2.

This works because step 3 only really affects 3 squares, and step 4 will undo all the weird "side effects" of step 2.

So, to do a general 3-cycle, all we have to do is figure out how to do step 2. That is, we need to be able to send any three numbers to any three squares we want. And, to do this, we are allowed to ignore all the other numbers, they don't matter anymore.

That's kinda hard. Let's try something easier: Can we send any single number to any square we want? As before, all the other numbers don't matter, I just want to be able to find a sequence of moves that can move some number to whatever square I want.

The solution to our predicament is the Spiral algorithm. Spiral can send any number we want to any square we want (while obeying PRs):

How would we come up with an algorithm like Spiral? Once again, we need to simplify our job. Can I send any number I want to the center square? If I can figure out how to do that, then I'm done! All I have to do is:

1. Find the moves I need to move my number to the center.
2. Find the moves I need to move the number in the goal square to the center.
3. Do the moves in step 1, then do the moves in step 2 in reverse.

This will bring my number to the center, and then the goal square.

Now I just need to figure out how to bring my number to the center. The idea is that I'm going to come up with a nice procedure that will bring my number closer to the center. Then if I keep doing that, my number will keep getting closer and closer to the center. Eventually, it will be right at the center!

Welp, here's my Spiral algorithm:

1. Bring my number to the lower-left quadrant of the rotating Y block.
2. Rotate X.
3. Repeat until at center.

That's it! Let's see how this plays out.

First, I keep rotating Y until my number is in the red region, which is the lower-left part of the rotating Y block.

Now, I rotate X just once.

If I keep doing this, my number eventually reaches the center. It kinda looks like a spiral. That's why I call this Spiral.

Question of the Day: Why does this work? Why is it that if I do those steps, the number must get closer to the center?

We need to figure out when the distance changed. It's when I did the X move:

The distance changed from $d$ to $d^\prime$. I need to prove that $d^\prime < d$.

I only need to focus on the X move. Also, I marked the two centers of the board as $c_x$ as $c_y$. This will be very useful.

I don't really care about the grid anymore. To help me out, I drew a circle at $c_y$ with radius $d$, because I know my number starts on the lower-left arc of this circle (in bold).

At this point I guess I can throw out the whole board too.

Next I needed to get rid of that X move and turn it into math somehow. Here, I turned it into an isosceles right triangle. This makes sense because during the X move, the distance to $c_x$ doesn't change, and it's a 90 degree turn.

Here I'm going to do something tricky. I'm going to make a new point called $c_y^\prime$. It's the point you get when you rotate $c_y$ 90 degrees clockwise around $c_x$. But why would I ever make a new point? Well look:

These two angles I marked are equal, right? You get both of them by subtracting a common angle from a right angle. But then...

Amazing, these two triangles are congruent! That means...

This missing length from $c_y^\prime$ to the number must be the same as $d^\prime$ by my congruent triangles! Now let's erase a bunch of the noise in my diagram:

Now I'm going to assume that each square's side length is one. Then the distance between $c_y$ and $c_y^\prime$ must be $\sqrt{2}$.

Finally, I will mark an angle $\theta$:

Remember that my number started on the lower-left arc of the circle, so that's why $\theta$ can't be more than $45^\circ$.

Ok I'm lost, what were we doing again? Right, we wanted to prove that $d^\prime < d$. At this point, we have an angle, two adjacent sides, and we need to compute $d^\prime$... I wonder how we can do that...

$$\Huge \text{Surprise! It's the Law of Cosines!}$$

By the Law of Cosines:

$$d^\prime = \sqrt{d^2+2 - 2\sqrt{2}d\cos\theta}$$

We need to prove that this is less than $d$, or:

$$\sqrt{d^2+2 - 2\sqrt{2}d\cos\theta} < d$$

Now we just need some nice algebra to manipulate this:

$$d^2+2 - 2\sqrt{2}d\cos\theta < d^2$$ $$2 - 2\sqrt{2}d\cos\theta < 0$$ $$2 < 2\sqrt{2}d\cos\theta$$ $$1 < \sqrt{2}d\cos\theta$$ $$d\cos\theta > \frac{\sqrt{2}}{2}$$

How do I prove this? Well I know two things:

1. $d>1$. Otherwise, the number is already at the center, so the algorithm would have stopped already.
2. $\cos\theta > \dfrac{\sqrt{2}}{2}$. That's because $0 < \theta < 45$.

If I multiply these two things, I get exactly $d\cos\theta > \dfrac{\sqrt{2}}{2}$. QED.

• So, the distance to the center decreases with every iteration.
• Thus, the distance to the center is eventually zero (because there are a finite number of possible distances).
• Therefore, Spiral is a terminating algorithm, and we have an algorithm that can send any number to the center.
• Ergo, we have an algorithm that can send any number to any square.

Yay! Wait now what?

Ok so, we wanted to be able to send any three numbers to any three squares. What we can do now is send any one number to any one square. We have to use Spiral three times, somehow, without messing up every previous number. But how?

Before we go on, I want to look at one more algorithm, called Cycle. It's defined as: $$(YX)^4 = YXYXYXYX$$ It's a very simple 8-move algorithm. What does it do? Well imagine that there's some sort of "conveyor" belt running around the board:

Cycle will move all the numbers $n-3$ squares "counter-clockwise":

It's actually not too hard to prove that it does this for all $n$. Something we call the "cyclic order" of all the numbers in the belt stays the same every time we do $YX$, and using some math we can find out how much each number moves after every $YX$.

Why is Cycle so important? Because it doesn't move a lot of numbers. That will give us more maneuverability. And with that, we're ready to describe...

Part IV: The Spiral-Cycle Algorithm

The Spiral-Cycle Algorithm sends three numbers to any three squares I want. It is a combination of Spiral and Cycle. Very similar to the Spiral algorithm, this won't happen directly. Instead, I will choose three set squares, and show that I can always move any three numbers to them. I will call these set squares the intermediate squares.

My ultimate plan will be:

1. Use Spiral-Cycle to find a sequence of moves that will send my three numbers to the three intermediate squares.
2. Use Spiral-Cycle to find a sequence of moves that would send the three numbers in the goal squares to the intermediate squares.
3. Execute the moves in step 1, then execute the moves in step 2 in reverse.

This will send my three numbers to the three goal squares via the intermediate squares. Now I just need to choose my intermediate squares and figure out how to get my numbers there.

For odd $n$, I choose these three:

For even $n$, I choose these three:

In both cases, the first of my intermediates is in the upper-left corner, and the third intermediate is at or close to the center of rotation of $X$. The third intermediate square is as close as possible to the first one, in the first column. In the odd case, that means it has to be two squares below because of PRs (if $n$ was odd and I tried to cycle three numbers that weren't in the same parity, it would be impossible).

I will now describe, roughly, the Spiral-Cycle algorithm:

1. Use Spiral to move the first number to the top-left.
2. Use an alternating Spiral to bring the second number to the center of rotation of $X$ for odd $n$, or the upper square in the center for even $n$.
3. If the first number was moved to the bottom-left due to the previous step, move it back to the top-left via $X^{-1}$ for odd $n$, or $X^{-1}Y^{-1}$ for even $n$.
4. Use an alternating Spiral to move the second number to bottom-right corner for even $n$, or the square above that corner for odd $n$.
5. If the first number was moved to the bottom-left at the end of the previous step, execute $X^{-1}$ to move it back to the top-left corner.
6. Execute $XY^{-1}X^{-1}$. This will bring my second number to the second intermediate square.
7. If the third number is now in the leftmost column, then move it out using $XY^2XYXY^{-1}X^2Y^{-1}XY^{-1}X^{-1}$ for odd $n$, or $XY^2X^{-1}Y^{-1}XY^{-1}X^{-1}$ for even $n$.
8. If the third number lies somewhere on the bottom row or right edge, execute $Y$ until it does not.
9. Run Spiral alternated with Cycle to get the third number to the center of rotating of $X$.
10. Execute Cycle if you need to and terminate.

Obviously this is confusing, especially since there are two new things: An "alternating Spiral", and "Spiral alternated with Cycle". Let's go over both.

• In a normal Spiral, every iteration starts by moving the number to the lower-left quadrant and then executing $X$. In an alternating Spiral, it is the same procedure, but every other iteration I instead move the number to the upper-left quadrant and then execute $X^{-1}$. Basically, I'm doing a flipped version of Spiral every other time.
• In a Spiral alternated with Cycle, I do an reverse Cycle before every time Spiral wants to use an $X$ move, and then do a Cycle before every time Spiral wants to use a $Y$ move.

These extra things are here to make sure the numbers we place stay where they are. Let's see how this works in practice.

First I do a Spiral to move my first number to the first intermediate.

Now I'm looking at the second number. Here it looks like I'm doing Spiral normally... but once I move $X$, something awful happens:

Oh no! The first number moved away to the bottom-left. Now I'm going to flip Spiral, so next time it will move back. Here I'm going to move my second number to the upper-left quadrant this time.

Now this time, I'm going to do $X^{-1}$ instead of $X$, and this will move the first number back to where it was.

I just have to keep doing this until my Spiral is done, and my second number ends up here:

I do $XY^{-1}X^{-1}$, and my second number can now join the first number happily:

Now I just need to somehow get the third number to the center...

Here I'm basically doing Spiral normally, except now I'm pretty much always using the top-left quadrant (always flipped version), because this quadrant doesn't intersect with Cycle's belt.

After I move my third number inside the quadrant, the next step of Spiral would be to execute $X^{-1}$. But this is terrible, because both of the first two numbers will move away, and this time that's basically unfixable. The trick is to now use Cycle in reverse to hide my first two numbers in the last column:

Now I can freely move the $X$ rotating block without moving the first two numbers.

Now the next step in Spiral is to move $Y$ until the number is in the upper-left quadrant again. But doing any $Y$ moves will move my first two numbers again. That's why now I have to use Spiral, which will move my two numbers back to where they were:

Now I am free to use the rotating $Y$ block! Rinse and repeat until my third number is where it needs to be:

We made it! That's the Spiral-Cycle algorithm. Let's recap:

• We now have an algorithm that can send any three numbers to any three squares, subject to PRs.
• So, we can always send any three numbers to three squares that we know can be 3-cycled.
• Thus, any three numbers can be 3-cycled, respecting PRs.
• Therefore, we can execute any even permutation.
• Ergo, the NRP is solved over all $n \times (n+1)$ boards with $n \times n$ rotating blocks for $n \geq 4$.

What about boards that have more moves than those like $n \times (n+1)$ boards with $n \times n$ rotating blocks? Like, maybe a $6 \times 6$ board with $4 \times 4$ rotating blocks? How can we extend our solution from the "hardest NRP" to the very general case?

As it turns out, it's not too bad! I will leave out the details, so treat it as a fun little exercise to the reader. Remember, we basically have the ability to execute any permutation we want within a $n \times (n+1)$ board with $n \times n$ rotating blocks. How can we use this fact to solve, say, a $(n+1) \times (n+1)$ board with $n \times n$ rotating blocks? Here are some cool ideas:

• Like before, if we can show that we can do any 3-cycle, we're done. Can we somehow extend the Spiral-Cycle algorithm?
• Could something similar to a Bubble Sort algorithm work?
• Can we use an inductive argument?

That's gonna wrap up the general case. Let's move on to...

---

Part V: Special Cases

We'll cover all the easy ones first.

$2 \times n$ board with $2 \times 2$ rotating blocks, $n \geq 4$

Super easy. All initial configurations are solvable. Take any $4 \times 2$ sub-board, and label the possible moves from left to right $X$, $Y$, and $Z$. Then the following algorithm will switch two numbers: $$XYZ^{-1}Y^2X^{-1}Z^{-1}YZ^2Y^{-1}$$

$m \times n$ board with $2 \times 2$ rotating blocks, $m,n \geq 3$

It's kinda funny that I'm considering the classical NRP as a special case, kinda because it is. Anyway, this is super easy. All initial configurations are solvable. Consider a $3 \times 3$ sub-board, and let $X$ rotate the lower-left $2 \times 2$ block, $Y$ rotate the upper-right block, and $Z$ rotate the lower-right block. The following algorithm switches two numbers: $$XY^{-1}X^{-1}YZ$$

$m \times n$ board with $3 \times 3$ rotating blocks, $m,n \geq 4$

All numbers must start in the correct parity, and the initial configuration must be an even permutation. Nothing we didn't expect, so we just need a 3-cycle algorithm and we can leave. Let $A$ rotate the upper-left $3 \times 3$ block, $B$ rotate the upper-right block, $C$ rotate the lower-left block, and $D$ rotate the lower-right block. Then the following is a 3-cycle: $$ADA^{-1}D^{-1}C^{-1}DA^{-1}D^{-1}AC$$ Those are all the easy cases. Now we move on to the scary cases.

$2 \times 3$ board with $2 \times 2$ rotating blocks

Out of the $6!$ possible permutations of the 6 numbers, only $5!=120$ are actually solvable configurations! Not easy to prove. Fortunately, Jaaps Scherphuis solved this special case as it appears a lot in Rubik's Cube solving. Here are his proofs:

https://www.jaapsch.net/puzzles/pgl25.htm

$3 \times 4$ board with $3 \times 3$ rotating blocks

This one I had to tackle myself. It's really shocking. Since rotating block size is odd, numbers stay in their own parity, so you'd think that there are $6! \cdot 6!$ possible solvable configurations, right?

Oh no. Only $6!$ are solvable.

Exactly. That means that if you solve the numbers in one parity, the size numbers in the other parity will automatically solve themselves. How the heck would you prove this?

Honestly I have no idea how I thought of this. I constructed two movement-graphs:

Ok let's dissect this:

• Every $3 \times 4$ grid is a possible state of the board in terms of either the red lines or the blue lines I'm looking at.
• Every red or blue line represents a pair. A pair is a set of two connected numbers/squares. The two numbers will stay connected as you move them around. It's like a very stretchy rope.
• All the boards with a red line depict every possible single pair between two numbers, within the even parity. That means we're only considering pairs between numbers within these squares:

• All the boards with the blue lines depict every possible way to pair up the six numbers in the other parity into three pairs. In other words, it's every way to partition the white squares in the picture above into sets of two.
• Every black line between two boards is just a move. One board is before the move, and the other is after a move. It's either an $X$ move or a $Y$ move. Each move will move the pair(s) around.

You probably noticed this already, but the really importantly cool part here is that the two graphs look the same. In math speak, they're basically isomorphic structures. (You might be asking yourself if the moves between the boards are the same in each graph. You can verify that for yourself.)

So what does this mean? Let's look at this sort of pairing:

If you look carefully, these are two corresponding pairings according to the two graphs I made. That means that no matter what moves I make, if I know where the red pair is, I know where all the blue pairs are. I might not know which blue pair contains which numbers, or what order the numbers are in, but I just know where they are.

That means, if I make a sequence of moves so that the red pair returns to where it started, the blue pair must stay the same.

Using the specific pairing locations in the picture above, this means that no matter what moves I make, if the numbers in the top-left and bottom-left end up in the top-left and bottom-left (i.e. red pair stays the same), then I know instantly where the blue pairs are. Since two paired numbers stay paired, that means that if I also know the number in the middle-left square (in between the two red-paired numbers), I must also know the exact identity of the number in the square that it's paired with, which is the number in the center of rotation of Y.

This is really weird to think about but really important so I'm going to rephrase this. If I know the three numbers in the left column, and establish a system of pairs as in the diagram above, then:

• The number in the middle of the left column is always bound (paired) to this mysterious unknown number.
• If I make some moves that keeps the red pair where it is, it will also preserve the blue pairs.
• If the number in the middle of the left column stays there, then that makes the blue pair from that square to the center of Y unique.
• That means that in that case, the number in the center of Y is still the mysterious number.
• In other words, if I make a bunch of moves that doesn't change the three numbers in the first column, it also won't change the number in the center of Y. So the number here is actually unique.
• To rephrase, if you tell me the identities of the numbers in the first column, then there is only one possible number that could be in the center of Y, if it exists.
• Therefore, given the numbers in the first column, I can deduce the number in the center of Y.

Lemma: The number in the center of rotation of Y is uniquely determined by the numbers in the first column.

How would I "deduce" it? Kinda by cheating. Let's say you told me the numbers in the first column were 6, 7, and 8. Basically we now play the NRP starting from a solved board, and cleverly make moves so that 6, 7, and 8 make up the first column.

I see that the number in the center of Y is 5. So, it's a possible number that could be there given the 6, 7, and 8. But it's also the only possible number that could be there, since it's unique. Therefore, we "deduce" that the only possible number that can be there is 5, given that 6, 7, and 8 are in the first column.

Is there a neat formula you can follow instead, so you don't have to physically play the NRP to find it out? Well, you could kinda use the two movement graphs to figure it out a bit quicker, but besides that I honestly don't know.

Anyways, the result we have now is really powerful. It's basically going to help limit the number of solvable configurations. In fact, I will now prove the following:

Theorem: Suppose the left column is solved. Then the entire board will be solved via $Y$ moves.

In other words, once we solve the left column, there are only four possible configurations left! And, one of them is the solved board, and we just have to keep rotating Y to get it!

If you think about it, it suffices to prove that once the left column is solved, and the number 2 is solved, the whole board is solved. That's because saying that the number 2 is solved will "lock" the correct rotation of Y, so everything else would indeed be solved.

Ok, so we're assuming the left column is solved, and the number 2 is solved.

Using the Lemma, the 7 is already solved, because we know the three numbers in the first column, and therefore "deduce" the 7, so that's good.

What happens if we put the 2 in the middle-left instead of the 5? What can we "deduce" will be in the center of Y?

Welp, looks like it's 12. So given the 1, 2, and 9, the location of 12 is fixed/unique. Now I "know" where 12 is, and undo my moves. We "deduce" that the 12 was solved:

What's our next conquest? Now we have to use a flipped version of our lemma, i.e. start using the right column and "deduce" the number in the center of X.

By making the right column 1, 2, and 5, I "deduce" that the number in the center of X must then be a 6. That means that the 6's location is fixed too now.

I'm excited! What if I now use the 1 with the 6 and put the 7 in between?

4 is solved!

Only one number left in this parity, so 10 is solved!

You can keep going by attacking the last three squares with the lemma, but I'm gonna cheat. If we do $Y$ and then say that the configuration we get is the solved position, then all our previous logic applies. That means that any number that could end up in the center of X, where the solved 6 was, must be solved. In other words, since the 6 is solved, the other three numbers are solved as well.

We're done! That means the entire board is determined by just the first column!

What does that mean? Let's count the number of possible configurations based on this. There are six choices for the top-left number, then five choices for the bottom-left number. There are also six choices for the number in between. In all, there are $6 \cdot 5 \cdot 6 = 180$ choices for the first column. Then there are four rotations of Y left, and so there are a total of $180 \cdot 4 = 720$ possible solvable configurations...

...and $720$ is $6$ factorial!!! We did it! By a counting argument, we proved that solving one parity must solve the other parity automatically. Black magic huh?

Conclusion

So yeah. We completely solved the Number Rotation Puzzle. Completely.

We've figured out all the possible solvability conditions, exhaustively. And for the rest, we've basically derived a very long and convoluted solving algorithm to solve any board that satisfies our parity restrictions. And, we cleaned up the special cases, some of which were rather unruly. We did it all with an amazing combination of abstract algebra, number theory, combinatorics, and even geometry and computer science.

I think we did more than that though.

The NRP is scary. Daunting. When I first imagined something like $10 \times 10$ rotating blocks, or even puny $4 \times 4$ rotating blocks, I was convinced that it wouldn't be humanly possible to figure out. And for sure, the rectangular board case would be completely impossible to even think about. With raw motivation and determination, I proved my past self dead wrong.

We managed to figure it all out using just simple, beautiful ideas. I contend that no advanced mathematics was done in the process. Not a single integral or summation, and no sight of a matrix or even a group. Math doesn't have to be scary or hard. That's not what it's about.

In light of this, I believe my solution tells many stories. For one, it's a classic story of determination. Second, it shows that amazing things can be done with simple things.

Most importantly, I believe that this is a testament to my strongest belief: That math is just all puzzles in the end. Yes, we solved a puzzle using math. But in a sense, you could say we tackled a math problem in the same way that we would solve a puzzle. We found a starting point and worked our way forward using clever arguments, wrestling the problem until the end.

Overall, it's been a crazy journey for me, and thanks to Regeneron, the end of this puzzle was a new beginning, and it gives me a lot of hope for my future, my passion for math, and my passion for puzzling.

Thanks for reading, y'all.

Answer 2

This somehow became a 2019 Regeneron STS Finalist project. The intent of this answer is to provide an easy-to-follow, layman's explanation to the mechanics of the solving process.

It's been an incredible journey. Enjoy!

---

Part I: Parity Restrictions

We'll first talk about figuring out easy ways to tell if a puzzle is not solvable. We can do this by examining a neat thing called parity. Parity is basically when things alternate. For example, because numbers alternate odd and even, this creates a parity. On a chessboard, every other square is black or white, so this also creates parity.

Let's look at this board:

Here, I colored the squares yellow and white so the parity is easy to see. There's something pretty special about parity here. Here, I marked a $5 \times 5$ rotating block. Can you imagine where each of the numbers move after the rotation?

• The 23 moves to where the 33 was.
• The 33 moves to where the 13 was.
• The 24 moves to where the 26 was.
• The 18 stays where it is.
• Etc.

Here's the cool thing: Numbers that started on yellow squares always end up on yellow squares, and numbers that started on white squares always end up on white squares. You can think of this as "if a number starts on one color of the parity, it can never escape it no matter how many times I move it around".

I wonder if this is still true if I change the rotating block size:

It's not true anymore! The 9 goes to the 24, and changes its color from yellow to white. So when is our cool parity thing true, then? For all odd rotating block sizes.

Conclusions:

• When the rotating block size is odd, numbers stay on their own parity.
• If the rotating block size is odd, then for the board to be solvable, every number must start on its correct parity.

What we just found is called a parity restriction (PR). It's just a restriction on the solvability of a board, which is based on a parity argument.

There are more PRs to be found! But where? The next PRs are hidden in something we call a permutation. You probably know this as a sort of reordering, like an anagram. Let's say I have the numbers:

$$1\ 2\ 3\ 4\ 5$$

I want to reorder the numbers by swaps, or a switching of two numbers. How many swaps do I need to get the numbers like this?

$$2\ 4\ 5\ 3\ 1$$

Let's try this:

$$1\ 2\ 3\ 4\ 5$$ $$1\ 2\ 3\ 5\ 4$$ $$1\ 2\ 5\ 3\ 4$$ $$1\ 4\ 5\ 3\ 2$$ $$2\ 4\ 5\ 3\ 1$$

I did it in four swaps! Let's try another way: $$1\ 2\ 3\ 4\ 5$$ $$1\ 2\ 3\ 5\ 4$$ $$1\ 2\ 4\ 5\ 3$$ $$1\ 4\ 2\ 5\ 3$$ $$5\ 4\ 2\ 1\ 3$$ $$5\ 4\ 2\ 3\ 1$$ $$2\ 4\ 5\ 3\ 1$$

This time I did it in six swaps. That's interesting. Is the number of swaps I'll need always an even number? Yes!!! That means the parity of the permutation $2\ 4\ 5\ 3\ 1$ is even.

Let's make a single swap:

$$4\ 2\ 5\ 3\ 1$$

What is the parity of the permutation now? Well, if we always needed an even number of swaps before, then now we'll always need an odd number of swaps. That means that parity of this permutation is odd!

(It's not that easy to prove that an even permutation always needs an even number of swaps, or that an odd permutation always needs an odd number of swaps. I think the easiest way to do it is to count the number of pairs of numbers that are not in order, e.g. the 4 and 3 are not in order in $4\ 2\ 5\ 3\ 1$ because the 4 should come after the 3, as $3 < 4$. Then, see how this number's parity changes after a single swap!)

So our second parity restriction is all about the parity of permutation. Every move we make does a permutation, because it reorders the numbers. What we want to know is, what is the parity of this permutation? In other words, how many swaps does it do?

For example, rotating a $2 \times 2$ block can be done in 3 swaps (odd permutation), and rotating a $3 \times 3$ block can be done in 6 swaps (even permutation). We care a lot about this because if my rotating blocks do only even permutations, then the starting board has to be an even permutation for it to be solvable! It makes sense because doing multiple even permutations will result in an even permutation. Each time I'm doing an even number of swaps, so the total number of swaps will be even.

With this in mind, what we want to know is when exactly will the permutation be even? For what rotating block sizes $b \times b$ will moves execute even permutations by doing an even number of swaps? To do that, we have to analyze how the numbers move around.

Here is a $5 \times 5$ rotating block. I highlighted all the numbers that move around in green.

What's important to note here is that the numbers move around in 4-cycles. For example, notice how 5 goes to 9, 9 goes to 31, 31 goes to 27, and 27 goes back to 5. Visually, $5 \to 9 \to 31 \to 27 \to 5$. We can notate this as $(5\ 9\ 31\ 27)$. We call this a 4-cycle because it's a "cycle" with four numbers.

How many swaps do you need to do a 4-cycle? As it turns out, you only need three! That means that 4-cycles are odd permutations. So, to find out the parity of the whole move's permutation, I just need to figure out how many 4-cycles it does. If there are an odd number of 4-cycles, then the whole permutation must be odd (because odd number of odd permutations is odd. Think of multiplication!), and if there are an even number of 4-cycles, then the whole permutation must be even (because even number of odd permutations is even).

To count the number of 4-cycles, there are two different cases we need to consider.

---

Case 1: $b$ is even.

If the rotating block size is even, then every number gets moved (unlike the picture above). There are $b^2$ numbers in total that get moved. So, the number of 4-cycles is just $b^2/4$. How do I tell if this number is odd or even?

I know $b$ is even, so I can write $b$ like $b = 2k$, where $k$ is a sort of dummy variable that I know is an integer. Then $b^2/4 = (2k)^2/4 = k^2$. Now it's easy. $k^2$ is even when $k$ is even, and it's odd when $k$ is odd. Looking back at $b = 2k$, we see that $k$ is even when $b$ is divisible by 4, and $k$ will be odd when $b$ is even but not divisible by 4.

Conclusion: For even $b$,

• If $b$ is divisible by 4, moves execute even permutations.
• Otherwise (when $b$ leaves a remainder of 2 when divided by 4), moves execute odd permutations.

Onto the second case!

---

Case 2: $b$ is odd.

Now there's a hole in the middle because the number in the center of the block doesn't move. Now only $b^2-1$ numbers move around in 4-cycles. Then the number of 4-cycles is just $(b^2-1)/4$.

Now we use the same trick as before. Since $b$ is odd, I can write $b$ as $b = 2k+1$. Then: $$(b^2-1)/4 = \frac{(2k+1)^2-1}{4} = \frac{4k^2+4k}{4} = k^2 + k = k(k+1)$$ Hey that's neat! $k(k+1)$ is a product of two consecutive integers. That means that it's always even!

Conclusion: When $b$ is odd, moves ALWAYS execute even permutations.

---

Yay! That's our second PR. But we're not done quite yet! Because, there's a hidden third PR. Where could it be? It's actually something you get by "combining" the previous two PRs!

Remember that for odd $b$, all numbers stay in their own parity? And that, for odd $b$, all moves are even permutations? What if I analyze only how the numbers move in one of the parities? Is the permutation within a parity still even, or is it odd? If it's even, then each parity's initial permutation must be even for the board to be solvable!

This will be a little trickier. In total we know that $b^2-1$ numbers are moved. But since we're only looking at a single parity, we're only considering half of those. So we divide by 2, to get $(b^2-1)/2$ numbers moved, and then we divide by 4 to count the number of 4-cycles inside the parity, to get $(b^2-1)/8$.

Once again, let $b = 2k+1$. Then: $$(b^2-1)/8 = \frac{(2k+1)^2-1}{8} = \frac{4k^2+4k}{8} = \frac{k(k+1)}{2}$$ When is this even or odd? It's hard to tell. Well, $k$ is either even or odd.

If $k$ is even, then $k = 2l$, and $\frac{k(k+1)}{2} = l(2l+1)$. This is even when $l$ is even, i.e. $l = 2x$, $k = 2l = 4x$, $b = 2k+1 = 8x+1$, so $b$ must leave a remainder of $1$ when divided by 8. On the other hand, it is odd when $l$ is odd, i.e. $l = 2x+1$, $k=2l=4x+2$, $b = 2k+1 = 8x+5$, so $b$ must leave a remainder of 5 when divided by 8.

If $k$ is odd, then $k = 2l+1$, and $\frac{k(k+1)}{2} = (2l+1)(l+1)$. This is even when $l$ is odd, i.e. $l = 2x+1$, $k = 2l+1 = 4x+3$, $b = 2k+1 = 8x+7$, so $b$ must leave a remainder of 7 when divided by 8. On the other hand, it is odd when $l$ is even, i.e. $l = 2x$, $k = 2l+1 = 4x+1$, $b = 2k+1 = 8x+3$, so $b$ must leave a remainder of 3 when divided by 8.

Conclusion:

• For odd $b$, moves execute even permutations on a single parity when $b$ leaves a remainder of 1 or 7 when divided by 8. Otherwise, when $b$ leaves a remainder of 3 or 5, moves execute odd permutations.
• For odd $b$, if $b$ leaves a remainder of 1 or 8 when divided by 8, each parity must be an even permutation of their respective solved states in order for the board to be solvable.

---

Let us now summarize the PRs.

• If $b$ has remainder 2 when divided by 4, no conditions.
• If $b$ is divisible by 4, the initial configuration must be an even permutation of the solved board.
• If $b$ has remainder 3 or 5 when divided by 8, then the initial configuration must be an even permutation of the solved board, and every number must lie in its correct parity. However, there are no additional restrictions within each parity.
• If $b$ has remainder 1 or 7 when divided by 8, then the board must be an even permutation, and every number must lie in its correct parity. In addition, each parity in isolation must be an even permutation of the solved configuration of the parity.

Are there any other restrictions? Yes, but only for smaller boards. As it turns out, the parity restrictions are, in general, sufficient for determining whether or not a board is solvable. Now we just need a general solving algorithm. Somehow.

---

Part II: The Hunt

To slay a dragon, you need a good weapon. Our weapon in this case will be the 3-cycle. As you can probably infer, it's just a cycling of three numbers: $$(1,2,3) \to (2,3,1)$$ Why do we really want to be able to do 3-cycles? Why not 2-cycles, which are just swaps? Aren't 2-cycles more powerful since we can definitely always win if we can switch any two numbers we want?

Yes, they are more powerful. Unfortunately, we have already proven that getting a 2-cycle is basically impossible! Remember that in many of the cases we described in our PRs, moves can only do even permutations. So, very often, there will never be an algorithm that can do an odd permutation. What's a 2-cycle? A single swap, i.e. an odd permutation! If we want to be general, we unfortunately can't look for 2-cycles.

The next best thing is the 3-cycle. It's made up of two swaps, which is perfect because if we can do any 3-cycle we want, then we can do any even permutation we want. So, we're on the hunt for a good general 3-cycle algorithm, i.e. a way to come up with a sequence of moves to execute any 3-cycle we want.

Where should we start looking? And, on what type or size of board should we be searching? We can't search all of them at once, can we? We need to narrow down our scope to something feasible. That's why we should think about the type of NRP that would probably be the "hardest" to find a 3-cycle. What's the hardest possible NRP you could think of?

Well, something like a $5 \times 5$ board with $5 \times 5$ rotating blocks would be too easy. What if we made it a bit bigger? Like, $5 \times 6$ board with $5 \times 5$ rotating blocks?

Oof! Suddenly it's almost impossible! It's so cramped. There are only two rotations we can make, and each one moves around literally $2/3$ of the numbers! This is our hardest case because there's very little maneuverability. We should be analyzing this minimal case, the $n \times (n+1)$ board with $n \times n$ rotating blocks, because if we can figure out how to solve hard NRPs like this, then NRPs with larger boards (but same rotating block size) should become pretty easy.

For future reference, we're going to call the move on the left $X$, and the move on the right $Y$. $X$ means a single turn counter-clockwise, $X^2$ means turn it twice, and $X^{-1}$ means turn it clockwise. $XY^2$ would mean do $X$, then $Y$ twice.

Alright, now we have a clear goal in sight. How can we find a general 3-cycle algorithm in the hardest case? Actually that's kinda hard, right? Let's see if we can tackle something easier. How can we find any 3-cycle algorithm in the hardest case? If we can't do the latter, we definitely can't do the former, so this is a good place to start.

Well, this is still kinda hard. Let's try to make our job even easier. To do that, we need to talk more about permutations.

We know a permutations is kinda like a reordering:

$$1\ 2\ 3\ 4\ 5 \to 3\ 4\ 5\ 2\ 1$$

But we can also look at it like a function. So $1$ becomes 3, $2$ becomes $4$, etc. We can model it like a neat table or matrix:

$$\begin{pmatrix}1&2&3&4&5\\3&4&5&2&1\end{pmatrix}$$

What's cool is that this allows us to see a bunch of cycles: $$1 \to 3 \to 5 \to 1$$ $$2 \to 4 \to 2$$ Though we usually like to notate them like this: $$(1\ 3\ 5)$$ $$(2\ 4)$$ So this permutation has both a 3-cycle and a 2-cycle. What happens when you execute this permutation twice? Then the 2 goes to 4 but goes back to 2, so the 2-cycle kinda dies out. But the 3-cycle is still there, because if you advance a 3-cycle twice, you still have a 3-cycle!

Let's look at another permutation:

$$\begin{pmatrix} 1&2&3&4&5&6&7&8 &9 &10&11&12&13&14&15\\ 2&4&6&1&3&9&8&10&12&11&13& 5&14&15& 7\end{pmatrix}$$

This permutation can be decomposed into the following cycles:

$$(1\ 2\ 4)$$ $$(3\ 6\ 9\ 12\ 5)$$ $$(7\ 8\ 10\ 11\ 13\ 14\ 15)$$

We have a 3-cycle, a 5-cycle, and a 7-cycle. What happens when we repeat this permutation 35 times?

Since 35 is a multiple of 5 and a multiple of 7, both the 5-cycle and the 7-cycle return to nothing in the end. But since 35 is NOT a multiple of 3, the 3-cycle is still a 3-cycle! So, even though the original permutation was definitely not a 3-cycle, we can still get a 3-cycle by repeating it enough times.

What if instead of a 7-cycle, there was a 6-cycle? Then out trick wouldn't work anymore, because we would have to repeat it $5 \cdot 6 = 30$ times, and 30 is a multiple of 3.

So essentially, we simplified our task to this: Find an algorithm, that executes a permutation, whose cycle decomposition has only ONE cycle that is a multiple of 3, and this cycle must be EXACTLY a 3-cycle. Then, we must be able to repeat this algorithm enough times to eventually get a 3-cycle. Now we just have to find an algorithm that does just that.

Now what? How do we find such an algorithm?

Well hey, there's only two moves we can do here: $X$ and $Y$, basically. And, any algorithm we can execute here would basically look something like $X^{k_1}Y^{k_2}X^{k_3}Y^{k_4}X^{k_5}Y^{k_6}\ldots$, so... brute force? I'm not gonna come up with this myself!

#######################
#### NRP3finder.py ####
### Thomas Lam 2018 ###
#######################

import copy
from pprint import pprint

class Alg():  # An algorithm and corresponding effect
    def __init__(self, *args):
        if len(args) == 1:
            self.board = makeBoard(args[0])
            self.moveType = 'x'  # RotX or RotY next?
            self.moveList = []

        if len(args) == 3:
            self.board = copy.deepcopy(args[0])
            self.moveType = args[1]
            self.moveList = args[2][:]

    def move(self, turns):
        if self.moveType == 'x':
            self.board = rotX(self.board, turns)
            self.moveType = 'y'

        elif self.moveType == 'y':
            self.board = rotY(self.board, turns)
            self.moveType = 'x'

        self.moveList.append(turns)

    def executeMoves(self, moves):  # Execute a list of moves in sequence.  Syntax:  [1,2,3,1,2,1,3, etc.]
        for m in moves:
            self.move(m)

    def cloneMove(self, turns):  # Clone the algorithm and advance the clone by one move
        newAlg = Alg(self.board, self.moveType, self.moveList)
        newAlg.move(turns)
        return newAlg

    def permCycleLens(self):  # Compute the lengths of all cycles in the algorithm permutation and toss into an array
        return cycleLens(collapseBoard(self.board))

    def has3Cycle(self):  # Does it contain a 3 cycle?
        return 3 in self.permCycleLens()

    def hasUnique3Cycle(self):  # Does it have a unique 3 cycle?
        has3 = False  # Does it have a pure 3 cycle?
        num3 = 0  # Number of cycles of order divisible by 3
        for num in self.permCycleLens():
            if num == 3:
                has3 = True

            if num % 3 == 0:
                num3 += 1

        return has3 and num3 == 1

    def getUnique3Cycle(self):
        assert self.hasUnique3Cycle
        for cycle in cycleDecompose(collapseBoard(self.board)):
            if len(cycle) == 3:
                return cycle

    def getCycles(self):
        print cycleDecompose(collapseBoard(self.board))

def ppprint(x):
    pprint(x, width=40)

def makeBoard(b):   # Make b+1 x b NRP board
    board = []
    num = 0
    for i in range(b):
        row = []
        for j in range(b+1):
            row.append(num)
            num += 1
        board.append(row)

    return board

def collapseBoard(board):  # List out elements into a 1D array
    out = []
    for row in board:
        for i in row:
            out.append(i)

    return out

def cycleLens(arr):
    remaining = set(arr)
    output = []
    while len(remaining) > 0:
        length = 1
        num = remaining.pop()
        while 1:
            num = arr[num]
            if num not in remaining:
                break

            remaining.remove(num)
            length += 1

        output.append(length)

    return output

def cycleDecompose(arr):
    remaining = set(arr)
    output = []
    while len(remaining) > 0:
        num = remaining.pop()
        cycle = [num]
        while 1:
            num = arr[num]
            if num not in remaining:
                break

            remaining.remove(num)
            cycle.append(num)

        output.append(cycle)

    return output

def rotX(board, turns = 1):
    b = len(board)
    newBoard = copy.deepcopy(board)
    for i in range(b):
        for j in range(b):
            if turns == 1:
                newBoard[i][j] = board[j][b-1-i]

            elif turns == 2:
                newBoard[i][j] = board[b-1-i][b-1-j]

            elif turns == 3:
                newBoard[i][j] = board[b-1-j][i]

    return newBoard

def rotY(board, turns = 1):
    b = len(board)
    newBoard = copy.deepcopy(board)
    for i in range(b):
        for j in range(1,b+1):
            if turns == 1:
                newBoard[i][j] = board[j-1][b-i]

            elif turns == 2:
                newBoard[i][j] = board[b-1-i][b+1-j]

            elif turns == 3:
                newBoard[i][j] = board[b-j][i+1]

    return newBoard

# Testing

testAlg = Alg(3)
testAlg.executeMoves([1,1,1,3,1])

assert testAlg.has3Cycle()
assert not testAlg.hasUnique3Cycle()

testAlg = Alg(4)
testAlg.move(1)
assert not testAlg.has3Cycle()

print 'Congrats!  You didn\'t mess up!  Starting search...'

# Testing

b = int(raw_input('Board size: '))

algList = [Alg(b)]

found3Cycle = False
foundUnique3Cycle = False

while not foundUnique3Cycle:
    # Advance all algorithms
    newAlgList = []
    for alg in algList:
        newAlgList.append(alg.cloneMove(1))
        newAlgList.append(alg.cloneMove(2))
        newAlgList.append(alg.cloneMove(3))

    algList = copy.deepcopy(newAlgList)

    # Search for 3-cycles

    for alg in algList:
        if alg.has3Cycle() and not found3Cycle:
            print 'Found 3-cycle.'
            print alg.moveList
            found3Cycle = True

        if alg.hasUnique3Cycle() and not foundUnique3Cycle:
            print 'Found unique 3-cycle.'
            print 'Algorithm:',
            print alg.moveList
            print '3-cycle:',
            print alg.getUnique3Cycle()
            print 'All cycles:',
            print alg.getCycles()
            foundUnique3Cycle = True

For you computer people, my strategy here is that I'm putting all the possible algorithms on the small $n \times (n+1)$ board with $n \times n$ rotating blocks inside a big tree. At the top of my tree there's the nothing, empty algorithm. From there, I can assume that the first move is an $X$ move. There are three possibilities (branches) from there: Either $X$, $X^2$, or $X^{-1}$. Then, each of these branches splits into three more branches, because the next move is either $Y$, $Y^2$, or $Y^{-1}$. With this big tree, all I have to do is start searching from the top, going through every layer, and checking each possibility for an algorithm that does exactly what I want.

When I run it for many different values of $n$, I find that there are certain algorithms that keep showing up for multiple values of $n$. So I took those algorithms and ran them through a certain algorithm checker, which basically tests the algorithm over and over again for different values of $n$ to see when it works and when it doesn't. Here are my results:

No 3-cycles found for $n=2,\ 3$.

If $n=4$, use $XY^2X^{-1}YX^{-1}Y^2$. Otherwise, for $n \geq 5$:

• If $n$ has a remainder of $0$, $1$, or $2$ when divided by 6, use $XYXYX^2Y^2X^{-1}Y^{-1}$.
• If $n$ has a remainder of $2$, $3$, or $4$ when divided by 6, use $XYXY^2XY^{-1}X^2Y^{-1}$.
• If $n$ has a remainder of $5$ when divided by 6, use $XYXYXYX^2YX^2Y^2$.

By lots of testing, I found that these rules work for all $n$ up to 200. How would I know if they work for all $n$? It's provable but kinda annoying, so I'm leaving it out. Basically, we need to figure out how each of these algorithms behaves, and prove it behaves that way no matter how big the board is. Then, based on the behavior, we need to figure out the lengths of each cycle in the algorithm's permutation's cycle decomposition in terms of $n$.