All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Permuting a Square (Posted on 2004-11-08)
Given a 3x3 square with 9 distinct entries, can all permutations of the elememts in the square be reached when the only legal operation is to rotate a 2x2 subsquare 90 deg clockwise? (A rotation on the same subsquare may be done multiple times.) If not how many positions are attainable?
```Example, rotating the upper left 2x2 square.
1 2 3    4 1 3
4 5 6 -> 5 2 6
7 8 9    7 8 9
```

 See The Solution Submitted by Brian Smith Rating: 4.2857 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 3 of 9 |

This is equivalent to a mechanical puzzle, and so I will try some techniques advocated in David Singmaster's Notes on Rubik's Magic Cube.  The technique is to find sequences of moves that accomplish changes in a small number of positions of pieces. They usually involve alternating moves of adjacent faces, or in this instances, subsquares, that I'll call "quadrants"--the moveable segments of the puzzle.

I will designate rotating the top-left "quadrant" 90 degrees clockwise as a; the top-right as b; the bottom-left as c and the bottom-right as d.  I will designate doing any one of these three times in succession, thus making the equivalent of rotating 90 degrees counterclockwise, A, B, C and D respectively.

In all instances below, we start by designating the contents of the squares as:

`123456789`

calling this the pristine position.

`183426   adAD759   (cycle 2, 5, 8)`

That is, the sequence of rotating the top-left "quadrant" 90 degrees clockwise, followed by the bottom-right "quadrant", and then the same two "quadrants" in the same order counterclockwise, results in the 2 going where the 5 had been; the 5 going where the 8 had been and the 8 going where the 2 had been, from the pristine positions.

What if we do abAB (as in each illustration, starting from the pristine position)?

`213465   abAB789   (swap 1 and 2; swap 5 and 6)`

This combination of rotations of the top-left and top-right "quadrants" results in the individual swapping of two pairs of pieces (numbers).  In understanding what is happening it helps to highlight the individual swaps in different colors.

The fact that we have a 3-cycle and a move combination that causes two pairwise swaps, together with the 4-cycle that constitutes a basic move, does eventually allow all permutations to take place, as we'll see below.

Continuing the playing around:

`351426   aBAb789   (swap 1 and 3; swap 2 with 5)`
`923416   aaddaadd785   (cycle 1, 5, 9)`
`823451   abAB adAD abAB769   (cycle 1, 6, 8)`

The above introduces the concept of a conjugation, a key element in Singmaster's Rubik's Cube solution that allows elementary switches to be performed in more than one specific location.  Here the sequence adAD, which cycles the pieces in the middle column, is prefaced and followed by a sequence that switches other pieces into, and then back out of, the area being cycled.

The following cycle will be used in our effort to confine a 3-cycle to one "quadrant", so that it can be combined with a 4-cycle to create a single pair swap:

`613452   aDAdabAB789   (cycle 1, 2, 6)`

The cycle immediately above: 1, 2, 6 would be more useful if 5 were part of the cycle rather than 6, so we want to conjugate 5 into the 6 position without affecting the other positions. We can take the mirror image of abAB (reflected in the middle horizontal axis) to swap 7 with 8 while swapping 5 with 6.  At the end of course the swapping has to be undone.  That mirror-image sequence to abAB is CDcd as the handedness is reversed in the reflected image:

`513426   CDcd aDAdabAB DCdc789   (cycle 1, 2, 5)`

Note that undoing CDcd reverses its moves in reverse sequence.  Because of the nature of this particular sequence (a cycle of 2) it could have just been repeated as CDcd.

But now that we've got a cycle of 3 within one "quadrant", we can combine it with a single 4-cycle move of that "quadrant":

`123546   CDcd aDAdabAB DCdc A789   (swap 4 and 5)`

This is the holy grail.  Any two pieces can be conjugated into those positions, then these steps can be made and then the pieces conjugated backward, and the two pieces selected will have switched spots, without affecting any already-placed pieces. At this point we have proved that any permutation is possible.  But we'll illustrate some steps just to be clear.

There are eight possible types of switch you might need to do to perform a given permutation: 1) corner with adjacent corner, 2) corner with opposite corner, 3) corner with center, 4) side with adjacent side, 5) side with opposite side, 6) side with center, 7) corner with adjacent side and 8) corner with non-adjacent side.

In each case the swapping will be done by either CDcd aDAdabAB DCdc A or by a reflection or rotation of that set of moves depending on which of the corners/edge pieces are involved.  In the sample moves, I'll stick with this particular set, and choose the corners/edge pieces that are amenable to this particular version.

`1. Corner with adjacent corner, say 1 and 3:321456   Abb CDcd aDAdabAB DCdc A BBa789`
`2. Corner with opposite corner, say 1 and 9:923456   Add CDcd aDAdabAB DCdc A DDa781`
`3. Corner with center, say 1 with 5--a little tricky:523416   dAD CDcd aDAdabAB DCdc A daD789`
`4. Side with adjacent side, say 2 with 6:163452   aaD CDcd aDAdabAB DCdc A dAA789`
`5. Side with opposite side, say 2 with 8:183456   aad CDcd aDAdabAB DCdc A DAA729`
`6. Side with center, say 2 with 5:153426   a CDcd aDAdabAB DCdc A A789`
`7. Corner with adjacent side, say 1 with 2:213456   aa CDcd aDAdabAB DCdc A AA789`

(of course that previous one could be shortened by combining the three A's at the end into one a.)

`8. Corner with non-adjacent side, say 1 with 6:623451   AD CDcd aDAdabAB DCdc A da789`

Of course when Singmaster was solving Rubik's cube, he had an actual cube to work with.  I did my experimentation on a computer simulation.  All it does is allow one to keep track of moves and their results:

startup:
s\$ = "123456789"
CLS

DO
LOCATE 1, 1
PRINT LEFT\$(s\$, 3)
PRINT MID\$(s\$, 4, 3)
PRINT RIGHT\$(s\$, 3)
DO: a\$ = INKEY\$: LOOP UNTIL a\$ > ""
IF a\$ = CHR\$(27) THEN END
SELECT CASE a\$
CASE "a"
s\$ = MID\$(s\$, 4, 1) + MID\$(s\$, 1, 1) + MID\$(s\$, 3, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 2, 1) + MID\$(s\$, 6)
CASE "b"
s\$ = MID\$(s\$, 1, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 2, 1) + MID\$(s\$, 4, 1) + MID\$(s\$, 6, 1) + MID\$(s\$, 3, 1) + MID\$(s\$, 7)
CASE "c"
s\$ = MID\$(s\$, 1, 3) + MID\$(s\$, 7, 1) + MID\$(s\$, 4, 1) + MID\$(s\$, 6, 1) + MID\$(s\$, 8, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 9)
CASE "d"
s\$ = MID\$(s\$, 1, 4) + MID\$(s\$, 8, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 7, 1) + MID\$(s\$, 9, 1) + MID\$(s\$, 6, 1)
CASE "A"
s\$ = MID\$(s\$, 4, 1) + MID\$(s\$, 1, 1) + MID\$(s\$, 3, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 2, 1) + MID\$(s\$, 6)
s\$ = MID\$(s\$, 4, 1) + MID\$(s\$, 1, 1) + MID\$(s\$, 3, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 2, 1) + MID\$(s\$, 6)
s\$ = MID\$(s\$, 4, 1) + MID\$(s\$, 1, 1) + MID\$(s\$, 3, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 2, 1) + MID\$(s\$, 6)
CASE "B"
s\$ = MID\$(s\$, 1, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 2, 1) + MID\$(s\$, 4, 1) + MID\$(s\$, 6, 1) + MID\$(s\$, 3, 1) + MID\$(s\$, 7)
s\$ = MID\$(s\$, 1, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 2, 1) + MID\$(s\$, 4, 1) + MID\$(s\$, 6, 1) + MID\$(s\$, 3, 1) + MID\$(s\$, 7)
s\$ = MID\$(s\$, 1, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 2, 1) + MID\$(s\$, 4, 1) + MID\$(s\$, 6, 1) + MID\$(s\$, 3, 1) + MID\$(s\$, 7)
CASE "C"
s\$ = MID\$(s\$, 1, 3) + MID\$(s\$, 7, 1) + MID\$(s\$, 4, 1) + MID\$(s\$, 6, 1) + MID\$(s\$, 8, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 9)
s\$ = MID\$(s\$, 1, 3) + MID\$(s\$, 7, 1) + MID\$(s\$, 4, 1) + MID\$(s\$, 6, 1) + MID\$(s\$, 8, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 9)
s\$ = MID\$(s\$, 1, 3) + MID\$(s\$, 7, 1) + MID\$(s\$, 4, 1) + MID\$(s\$, 6, 1) + MID\$(s\$, 8, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 9)
CASE "D"
s\$ = MID\$(s\$, 1, 4) + MID\$(s\$, 8, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 7, 1) + MID\$(s\$, 9, 1) + MID\$(s\$, 6, 1)
s\$ = MID\$(s\$, 1, 4) + MID\$(s\$, 8, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 7, 1) + MID\$(s\$, 9, 1) + MID\$(s\$, 6, 1)
s\$ = MID\$(s\$, 1, 4) + MID\$(s\$, 8, 1) + MID\$(s\$, 5, 1) + MID\$(s\$, 7, 1) + MID\$(s\$, 9, 1) + MID\$(s\$, 6, 1)
CASE "R", "r"
seq\$ = ""
LOCATE 2, 7: PRINT SPACE\$(70);
GOTO startup
END SELECT
seq\$ = seq\$ + a\$
LOCATE 2, 7: PRINT seq\$;
LOOP

Where R resets to a pristine board, Esc terminates and each letter does its corresponding move, with the capitals doing the lower case version three times.

 Posted by Charlie on 2004-11-08 15:14:56

 Search: Search body:
Forums (0)