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 |
solution
