Consider the goal 3x3 position:
You must reach this position by rotating 2x2 blocks by some multiple of 90 degrees like so:
Orientation of each individual number is preserved.
What is the strategy to solve this puzzle? How about for larger boards, such as this 6x6 board with 4x4 rotating blocks?
I'd like to observe that a "row by row" approach does not seem guaranteed to work, likely due to the dark forces of parity.
As an extension, what is the strategy if orientation of each number is NOT preserved with block rotation?
Answer
Update: Simon Tatham's Twiddle has been solved!
Almost complete answer, which solves for ALL board sizes, accounts for the variation in which orientation is not preserved with rotation, but cannot show how puzzles with larger block rotation can be solved.
Consider a puzzle of any size of side length $\geq 3$, with $2 \times 2$ rotating blocks. We can ignore orientation for now.
We prove that with orientation of numbers ignored, the puzzle is always solvable.
Firstly, in any $2 \times 2$ grid contained in the puzzle, there exists an algorithm to preform a 3-cycle on 3 of the numbers.
1 2 3
4 5 6
7 8 9
Converts to:
1 2 3
4 8 5
7 6 9
The 5, 6, and 8 got cycled.
The algorithm to preform this is as follows: Pick a $3 \times 3$ grid containing the 3 numbers in question, and orient the contained $2 \times 2$ grid so the 3 numbers, A, B, and C, are in these relative positions:
1 2 3
4 A B
5 C 6
Action X rotates the bottom-left four numbers counter clockwise, and action Y rotates the top-right four numbers counter clockwise. The algorithm is:
$XY'X'Y$
Which is demonstrated as follows:
1 2 3
4 A B
5 C 61 2 3
A C B
4 5 61 C 2
A B 3
4 5 61 C 2
4 A 3
5 B 61 2 3
4 C A
5 B 6
While this seems clever, I don't really have a completely logical explanation other than just proof by demonstration.
Now fun fact: The given 3 - cycle is equivalent to a swap of two adjacent numbers. Consider the $2 \times 2$ grid:
1 2
3 4
Now preform a 3 - cycle to obtain:
3 1
2 4
A single counter clockwise rotation reveals:
1 4
3 2
The 2 and the 4 are swapped. Thus, we can swap any 2 edge adjacent numbers, and now the proof that any board size can be solved is trivial...
...until we introduce non-preservation of orientation. Then it gets hard.
But, maybe not so hard, after a simple observation: If the puzzle is solvable, then once the numbers are sorted using the method previously described, the orientation of all numbers are either correct or at 180 degrees! Oh, and this time, I have proof!
Proof: Consider a number in the puzzle with correct orientation and position. Color the puzzle like a checkerboard, such that the square in which this number lies is black. If this number is moved by a rotation, it moves exactly one square, to a white square, and its orientation is changed by 90 degrees, to either 90 or 270. Another rotation brings this number back to black, and orientation is brought to either 0 or 180. Clearly, if this number is on its proper parity, then it will always have orientation of 0 or 180. In the state in which all numbers are sorted, all numbers are on their proper parity. Therefore, they must all have either correct orientation, or are oriented at 180 degrees.
We have a second observation: If the puzzle is solvable, then when the numbers are sorted, the number of numbers with 180 degree orientation is even.
Proof: Consider the sum of the degrees of the orientations of all the numbers in the puzzle. Each rotation changes the orientations of 4 numbers by 90, in one direction. This either adds or subtracts 90 * 4 = 360 degrees to the total sum. The solved state has a total orientation sum of 0, so any set of rotations must bring the total orientation sum to a multiple of 360. If the puzzle is sorted but there is an odd number of numbers with orientations of 180, then the orientation sum is 180 (mod 360), contradiction.
I now present an algorithm that orients 2 pairs of 2 numbers by 180 degrees, preserving position, like this:
1↑ 2↑ 3↑
4↑ 5↑ 6↑
To this:
1↓ 2↑ 3↓
4↓ 5↑ 6↓
Let action X rotate the left 4 numbers 90 degrees counter clockwise, and let action Y rotate the right 4 numbers 90 degrees counter clockwise. The algorithm is:
$XX, Y, XX, YY, X, YY$
Demonstration:
1↑ 2↑ 3↑
4↑ 5↑ 6↑5↓ 4↓ 3↑
2↓ 1↓ 6↑5↓ 3← 6←
2↓ 4→ 1→4← 2↑ 6←
3→ 5↑ 1→4← 1← 5↓
3→ 6→ 2↓4← 1← 5↓
3→ 6→ 2↓1↑ 6↑ 5↓
4↓ 3↑ 2↓1↓ 2↑ 3↓
4↓ 5↑ 6↓
Let's call this procedure A. Careful observation yields a logical explanation to explain the effects of this algorithm, but I... uh... will leave it as an exercise to the reader.
I can now demonstrate that using procedure A, we can orient 2 corner adjacent numbers by 180 degrees, like so:
1↑ 2↑ 3↑
4↑ 5↑ 6↑
To,
1↑ 2↑ 3↓
4↑ 5↓ 6↑
X and Y have the same definition from the last algorithm, and we also have procedure A. The algorithm is:
$AYAY'$
...which doesn't warrant much explanation at all, especially once I demonstrate:
1↑ 2↑ 3↑
4↑ 5↑ 6↑1↓ 2↑ 3↓
4↓ 5↑ 6↓1↓ 3→ 6→
4↓ 2← 5←1↑ 3→ 6←
4↑ 2← 5→1↑ 2↑ 3↓
4↑ 5↓ 6↑
This doesn't yet solve the puzzle, But let's call this procedure B.
I think we can all agree that if we can invent an algorithm to orient two adjacent numbers 180 degrees, we basically win the game for all board sizes. Right? Do I have to prove it?? Please don't make me, I think we can all imagine a dozen informal proofs for why it would definitely solve the puzzle... ;-;
Such an algorithm exists though! We can convert,
1↑ 2↑ 3↑
4↑ 5↑ 6↑
to,
1↑ 2↓ 3↓
4↑ 5↑ 6↑
Using this algorithm!
$X'BX$
Demonstration:
1↑ 2↑ 3↑
4↑ 5↑ 6↑4→ 1→ 3↑
5→ 2→ 6↑4→ 1→ 3↓
5→ 2← 6↑1↑ 2↓ 3↓
4↑ 5↑ 6↑
And that's it! We've proven that with $2 \times 2$ rotating blocks, we can logically solve all solvable boards of whatever size.
As it stands, the procedure for solving these puzzles is inefficient. To optimize, start by manually solving with a row-by-row approach from top to bottom until the last 2 rows. Then, start using a column-by-column approach from left to right until you are left with the unsolved $2 \times 2$ grid. Additionally, one can orient two side-adjacent numbers 180 degrees more quickly, by applying algorithm A, repositioning a wrongly oriented number, then reapplying A.
I absolutely do not want to think about larger rotating block sizes. That sounds horrifying and looks like puzzling hell. I'm proud of my contribution to the puzzling society as it stands (I couldn't find a strategy online), and you can try out the strategy here:
http://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/twiddle.html (Run by javascript)
A solution to larger block sizes, a generalization for any rotating block size, or a procedure more optimal than mine is welcome.
Sample Solve:
I have made extremely significant progress on the $N \times N$ board with $3 \times 3$ rotating blocks. There is only one special case that I cannot resolve.
Special case: $N=3$
Trivial.
Special case: $N=4$
See the bottom of this answer.
General case: $N \geq 5$
Our plan is as follows:
- Reduce the $N \times N$ board to a $5 \times 5$ board.
- Solve the case $N=5$.
Part I: Reduction
The board reduction process is rather simple. We simply need to reduce an $N \times N$ board to a $(N-1) \times (N-1)$ board, for some $N \geq 6$, and repeat this process. Really, we just need to solve the following squares:
For $N \geq 6$, the board is large enough to provide sufficient space and mobility to maneuver each individual "edge" number to its correct square, until the last 3 numbers along each edge. As you might expect, this is easily resolved with a simple intermediate construction. The details are left to the reader; We have bigger fish to fry!
Part II: $N=5$
Divide the squares of odd parity into the following classes:
Our scheme is as follows:
- Solve the four Class A numbers.
- Solve the eight Class B numbers.
- Maneuver the rest of the numbers into place with iterated commutators.
Step 1: Solve Class A
We need to solve the numbers $7$, $9$, $17$, and $19$. It is not hard to maneuver the first two one at a time. I recommend an intermediate construction to solve the next two numbers at the same time, in one move.
Step 2: Solve Class B
Trivial. Why?
If we restrict our allowed moves to only the rotations of the blocks centered at Class A squares (so they stay fixed), observe that the Class B squares form a $3 \times 3$ board, and our moves are just $2 \times 2$ rotating blocks. But we solved this already, remember?
Step 3: Solve the rest of the squares
I now present four algorithms in one:
The moves $X$ and $Y$ are described in the graphic above. If $A$ is some move, it is implied to be counterclockwise, and $A'$ is the clockwise variant.
Consider the following algorithm:
$$XYX'Y'\ XYX'Y'$$
This is reminiscent of Rubik's Cube commutators. It has the following effect:
Essentially, we have created a three-cycle.
This algorithm is one of a set of four algorithms. The other three come from reversing the direction of each move, or switching the side of each move. Essentially, our four algorithms are:
- $XYX'Y'\ XYX'Y'$
- $X'Y'XY\ X'Y'XY$
- $YXY'X'\ YXY'X'$
- $Y'X'YX\ Y'X'YX$
As for some guidelines as to what each one does:
- If your first move is counterclockwise, then the "slant line" of the three-cycle is from bottom-left to top-right. If your first move is instead clockwise, this diagonal slant line is in the other direction, from top-left to bottom-right.
- The side that your first move is on is the side that the central number moves to under the three-cycle.
Arguably, any of these four algorithms are already sufficient. The full set is just for your convenience. Really, any three numbers located on the even parity can be three-cycled by moving them into place using some intermediate moves, preforming our algorithm, then reversing our intermediate concessions. Though, I'd say it is quite likely that the game is solvable using these four algorithms alone.
Regardless, we must prove that three-cycles of even parity numbers will suffice to win the game for completeness.
Assume there exists a board, with odd parity solved, that is unsolvable with three cycles of even numbers, but solvable with other means. First, we follow our scheme, solving the numbers of odd parity, then using three-cycles to solve all numbers of even parity, except three of them. Then, preform three-cycles on the three unsolved numbers until one of them is solved. Since the game was unsolvable with three-cycles, we must have that the last two numbers remaining are unsolved, and are therefore switched. Hence, we have achieved a position in which two numbers of even parity are switched, and everything else is in the correct position. We must now prove that such a position cannot be reached from the solved state.
Every move, a block rotation, we make is virtually two simultaneous 4-cycles of numbers. When composed, we see that each move is itself a permutation of even parity. In the aforementioned board state, two and only two numbers were switched, indicating that there is a composition of moves resulting in an odd permutation. But our moves are even permutations, and no composition of these permutations can result in an odd permutation, hence the proof.
In layman's terms, we can imagine each $3 \times 3$ block rotation as a cycling of the numbers at the corners, and then a cycling of the numbers along the edges. The number in the center stays put. Each cycle itself can be "decomposed" into three switches of numbers. So, to get from 1234 to 2341, our switches look like 1234 -> 2134 -> 2314 -> 2341. So this cycle is an odd permutation. Since there are two of these cycles, we have an odd + odd = even permutation. In other words, each move we make contains an even number of switches. Now, if we start from the solved board, and we make moves to convert this to the board with only two numbers switched, then the net result is that we made one switch. That means that in total, using our moves, we must have made an odd number of switches. But each move made an even number of switches, contradiction.
I glossed over the fact that an even permutation cannot be odd; Any position reached with an even number of switches cannot also be reached with an odd number of switched. Trustworthy Wikipedia has some stuff on that: https://en.wikipedia.org/wiki/Parity_of_a_permutation
Sample Solve:
$3 \times 3$ rotating blocks: The final nail in the coffin
We still haven't solved the $4 \times 4$ board. Understandable, since each move permutes more than half the board. Nevertheless, it is possible!
For the same reasoning concerning the parity of permutations, it is impossible to switch two numbers while leaving everything else untouched. Hence, it suffices to find a family of three-cycles, and abuse them to solve everything.
Ignoring their clockwise counterparts, there are four legal moves. They are situated in the top-left, top-right, bottom-left, and bottom-right. Denote these counterclockwise rotations as $A$, $B$, $C$, and $D$ respectively.
I claim that the following 10-move algorithm is a three-cycle:
$$ADA'D'C'DA'D'AC$$
Obviously, this three-cycle is confined to one parity. It is rather trivial to rotate or mirror this algorithm to uncover a family of 8 different three-cycles, that encompasses both parities.
The above algorithm seems to fly out of nowhere. I'll show how one may motivate this algorithm. Go to https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/twiddle.html, set the game type to "4x4', rotating 3x3 blocks", then click "solve game" so you can follow along.
We first experiment with the natural commutator:
$$ADA'D'$$
Observe that this actually results in two swaps of numbers. Namely, $5$ and $10$ are swapped, and $7$ and $12$ are swapped.
We now would like to use this commutator, except to undo the swap of $5$ and $10$, and swap either the $7$ or $12$ with something else. This creates a three-cycle. The easiest way to do this is $C'A'$. This retains the $5$ and $10$ in the "hot zone", so their swap will be undone. Now, notice that the $7$ is also still in the hot zone, though $12$ is not. Hence, this will create the three cycle after we apply the commutator again with $ADA'D'$ and undo our intermediate steps with $AC$. Composing all these moves reveals the algorithm $ADA'D'C'A'ADA'D'AC$, which reduces to $ADA'D'C'DA'D'AC$.
As said before, this three-cycle kills the game. A quick solving scheme goes like this:
- Solve $1$, $3$, $8$, and $16$ with some clever maneuvering. After you solve the $1$ and $3$, it is easiest to separate $8$ and $16$, and then "prep" them by placing $8$ at the bottom-right corner, moving $16$ two squares to the left of it, and then $D$.
- Iterate $C$ until it can be observed that the $6$, $9$, $11$, and $14$ can be solved with a three-cycle. Of course, you will have to maneuver the three offending numbers carefully into place before you do this. Do not panic if you encounter a state where seemingly only two of these numbers are switched. The solution is to either $C$ or $C'$, one of them will reveal which three-cycle we need (Do you recall in the beginning of this answer the observation that a 3-cycle can be converted to a 2-cycle? This is a similar problem). Remember that while a single rotation is an even permutation acting on the board, it is actually an odd permutation when acting on a single parity. Hence, it is very possible for there to be two numbers of the same parity swapped during this step. Since we have not solved the other parity, we would conclude that in such a state, the parity of the permutation of both parities is odd. They will be both even once we solve the first parity.
- We're out of tricks. Monotonously abuse three-cycles on the other parity until the game is solved. Make sure you frequently use intermediate manipulations to speed up this process.
Sample solve:
And with that, I'm proud to say that $7/8$ of Simon Tatham's Twiddle variants have been annihilated! Now about those $4 \times 4$ rotating blocks... Eek.
The final level: $6 \times 6$ with $4 \times 4$ rotating blocks
Jaap Scherphuis discovered the following algorithm:
Consider a $ 5 \times 4$ board, long side horizontal. Let the two possible moves be $L$ and $R$. Then the following is a three-cycle:
$$RLRL'RLRL'RLRLLR'L'R'LR'L'R'LR'L'R'LL$$
In short:
$$X = RLRL'$$ $$Y = R'L'R'L$$ $$X^3L'Y^3L$$
This results in an extremely annoying three-cycle. Nevertheless, there is sufficient maneuvering space to get any three desired numbers into position (which can be the pattern of the three-cycle flipped, reversed, translated, etc.) and then perform our algorithm. This is extremely tedious. Regardless, we now have a winning strategy.
Sample solve:
https://www.youtube.com/watch?v=zhT3kYMQfLU
It's been a fun run. It surprises me how little research has been done on this game and its strategies, given the relatively intuitive mechanics. Granted, it is rather difficult to emulate the game mechanically, but I do think this nice combination game is pure enough to deserve an official name. I do hope that this game can be popularized a bit.
No comments:
Post a Comment