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

Home > General
Permuting a Square (Posted on 2004-11-08) Difficulty: 4 of 5
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 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:

123
456
789

calling this the pristine position.

What happens if we try the sequence adAD?  This:

183
426   adAD
759   (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)?

213
465   abAB
789   (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:

351
426   aBAb
789   (swap 1 and 3; swap 2 with 5)
923
416   aaddaadd
785   (cycle 1, 5, 9)
823
451   abAB adAD abAB
769   (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:

613
452   aDAdabAB
789   (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:

513
426   CDcd aDAdabAB DCdc
789   (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":

123
546   CDcd aDAdabAB DCdc A
789   (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:
321
456   Abb CDcd aDAdabAB DCdc A BBa
789
2. Corner with opposite corner, say 1 and 9:
923
456   Add CDcd aDAdabAB DCdc A DDa
781
3. Corner with center, say 1 with 5--a little tricky:
523
416   dAD CDcd aDAdabAB DCdc A daD
789
4. Side with adjacent side, say 2 with 6:
163
452   aaD CDcd aDAdabAB DCdc A dAA
789
5. Side with opposite side, say 2 with 8:
183
456   aad CDcd aDAdabAB DCdc A DAA
729
6. Side with center, say 2 with 5:
153
426   a CDcd aDAdabAB DCdc A A
789
7. Corner with adjacent side, say 1 with 2:
213
456   aa CDcd aDAdabAB DCdc A AA
789

(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:
623
451   AD CDcd aDAdabAB DCdc A da
789

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information