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.)
 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
CASE 6
CASE 7
CASE 8
CASE 9
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
CASE 7
prefix\$ = "AcA"
CASE 8
CASE 9
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
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
CASE 7
prefix\$ = "bcB"
CASE 8
prefix\$ = "C"
CASE 9
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:

`                                       253Start                                  817                                       496`
`                                       153dAD CDcd aDAdabAB DCdc A daD           827                                       496`
`                                       123a CDcd aDAdabAB DCdc A A               857                                       496`
`                                       123c CDcd aDAdabAB DCdc A C               457                                       896`
`                                       123ddC CDcd aDAdabAB DCdc A cDD           456                                       897`
`                                       123cdd CDcd aDAdabAB DCdc A DDC           456                                       798`
`                                       123dC CDcd aDAdabAB DCdc A cD             456                                       789                                                                              612Start                                  843                                       975`
`                                       162aa CDcd aDAdabAB DCdc A AA             843                                       975`
`                                       126aabb CDcd aDAdabAB DCdc A BBAA         843                                       975`
`                                       123bba CDcd aDAdabAB DCdc A ABB           846                                       975`
`                                       123 CDcd aDAdabAB DCdc A                  486                                       975`
`                                       123add CDcd aDAdabAB DCdc A DDA           456                                       978`
`                                       123cc CDcd aDAdabAB DCdc A CC             456                                       798`
`                                       123dC 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

 Search: Search body:
Forums (0)