perplexus.info :: General : Permuting a Square

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.)

re: solution (spoiler)

| Comment 5 of 9 |

(In reply to solution by Charlie)

If the digits 1 - 9 are placed randomly in the square, without regard to the rules of the puzzle, then some specific random permutation will be needed to return the numbers to their standard positions. This program does that. Rather than reflecting the moves given previously to get other swaps, it always uses the sequence for the swap of positions 4 and 5, with appropriate conjugation to get the pieces that are needed to be swapped into those positions. The conjugations are shown in the prefixes assigned. For example, to find the conjugation for swapping positions 3 and 8, look in the section headed ix = INSTR(s$, "3"), under CASE 8 (always the lower number within the "ix =", and the higher number in the CASE. In the case of 3 and 8, the prefix is bbC, so the sequence of moves is bbC, followed by the standard CDcd aDAdabAB DCdc A for swapping positions 4 and 5, and then cBB, to undo the effects of the bbC, but leaving the two desired pieces swapped.

DECLARE SUB move (seq$)
DECLARE SUB show (a$, b$)
DECLARE SUB usePref (p$)
DIM SHARED s$
startup:
s$ = "123456789"
CLS
RANDOMIZE TIMER
FOR i = 1 TO 9
j = INT(RND(1) * 9 + 1)
IF i <> j THEN
IF j < i THEN SWAP i, j
s$ = LEFT$(s$, i - 1) + MID$(s$, j, 1) + MID$(s$, i + 1, j - i - 1) + MID$(s$, i, 1) + MID$(s$, j + 1)
END IF
NEXT

show "Start", s$

ix = INSTR(s$, "1")
SELECT CASE ix
CASE 1
   prefix$ = "-"
CASE 2
   prefix$ = "aa"
CASE 3
   prefix$ = "Baa"
CASE 4
   prefix$ = "A"
CASE 5
   prefix$ = "dAD"
CASE 6
   prefix$ = "AD"
CASE 7
   prefix$ = "CAd"
CASE 8
   prefix$ = "Ad"
CASE 9
   prefix$ = "Add"
END SELECT
IF prefix$ <> "-" THEN
usePref prefix$
END IF

ix = INSTR(s$, "2")
SELECT CASE ix
CASE 2
   prefix$ = "-"
CASE 3
   prefix$ = "aabb"
CASE 4
   prefix$ = "ca"
CASE 5
   prefix$ = "a"
CASE 6
   prefix$ = "aaD"
CASE 7
   prefix$ = "AcA"
CASE 8
   prefix$ = "aad"
CASE 9
   prefix$ = "aadd"
END SELECT
IF prefix$ <> "-" THEN
usePref prefix$
END IF

ix = INSTR(s$, "3")
SELECT CASE ix
CASE 3
   prefix$ = "-"
CASE 4
   prefix$ = "bb"
CASE 5
   prefix$ = "abb"
CASE 6
   prefix$ = "bba"
CASE 7
   prefix$ = "bbac"
CASE 8
   prefix$ = "bbC"
CASE 9
   prefix$ = "bbadd"
END SELECT
IF prefix$ <> "-" THEN
usePref prefix$
END IF

ix = INSTR(s$, "4")
SELECT CASE ix
CASE 4
   prefix$ = "-"
CASE 5
   prefix$ = ""
CASE 6
   prefix$ = "D"
CASE 7
   prefix$ = "c"
CASE 8
   prefix$ = "d"
CASE 9
   prefix$ = "dd"
END SELECT
IF prefix$ <> "-" THEN
usePref prefix$
END IF

ix = INSTR(s$, "5")
SELECT CASE ix
CASE 5
   prefix$ = "-"
CASE 6
   prefix$ = "aD"
CASE 7
   prefix$ = "bcB"
CASE 8
   prefix$ = "C"
CASE 9
   prefix$ = "add"
END SELECT
IF prefix$ <> "-" THEN
usePref prefix$
END IF

ix = INSTR(s$, "6")
SELECT CASE ix
CASE 6
   prefix$ = "-"
CASE 7
   prefix$ = "cb"
CASE 8
   prefix$ = "ccb"
CASE 9
   prefix$ = "ddC"
END SELECT
IF prefix$ <> "-" THEN
usePref prefix$
END IF

ix = INSTR(s$, "7")
SELECT CASE ix
CASE 7
   prefix$ = "-"
CASE 8
   prefix$ = "cc"
CASE 9
   prefix$ = "cdd"
END SELECT
IF prefix$ <> "-" THEN
usePref prefix$
END IF

ix = INSTR(s$, "8")
SELECT CASE ix
CASE 8
prefix$ = "-"
CASE 9
prefix$ = "dC"
END SELECT
IF prefix$ <> "-" THEN
usePref prefix$
END IF

SUB move (seq$)
FOR posn = 1 TO LEN(seq$)
a$ = MID$(seq$, posn, 1)
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)
END SELECT
NEXT posn
show seq$, s$
END SUB

SUB show (a$, b$)
LOCATE , 40
PRINT LEFT$(b$, 3)
PRINT a$;
LOCATE , 40
PRINT MID$(b$, 4, 3)
LOCATE , 40
PRINT RIGHT$(b$, 3)
PRINT
END SUB

SUB usePref (p$)
suf$ = ""
FOR i = 1 TO LEN(p$)
c$ = MID$(p$, i, 1)
IF c$ >= "a" AND c$ <= "z" THEN
c$ = UCASE$(c$)
ELSE
c$ = LCASE$(c$)
END IF
suf$ = c$ + suf$
NEXT
mSeq$ = p$ + " CDcd aDAdabAB DCdc A " + suf$
move mSeq$
END SUB

Two examples are:

                                       253
Start                                  817
                                       496

                                       153
dAD CDcd aDAdabAB DCdc A daD           827
                                       496

                                       123
a CDcd aDAdabAB DCdc A A               857
                                       496

                                       123
c CDcd aDAdabAB DCdc A C               457
                                       896

                                       123
ddC CDcd aDAdabAB DCdc A cDD           456
                                       897

                                       123
cdd CDcd aDAdabAB DCdc A DDC           456
                                       798

                                       123
dC CDcd aDAdabAB DCdc A cD             456
                                       789
                                       
                                       612
Start                                  843
                                       975

                                       162
aa CDcd aDAdabAB DCdc A AA             843
                                       975

                                       126
aabb CDcd aDAdabAB DCdc A BBAA         843
                                       975

                                       123
bba CDcd aDAdabAB DCdc A ABB           846
                                       975

                                       123
 CDcd aDAdabAB DCdc A                  486
                                       975

                                       123
add CDcd aDAdabAB DCdc A DDA           456
                                       978

                                       123
cc CDcd aDAdabAB DCdc A CC             456
                                       798

                                       123
dC CDcd aDAdabAB DCdc A cD             456
                                       789

Note in the second example, that the 4 was in position 5, so on the fourth step, no conjugation was necessary. Also every time a digit is found in its correct place already, a whole step (row of moves) is not needed.

Edited on November 8, 2004, 5:51 pm

Posted by Charlie on 2004-11-08 17:50:11

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info