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(2): tiny simplification thought

| Comment 6 of 9 |

(In reply to re: tiny simplification thought by Charlie)

A computer search has found that only 120 of the 720 conceivable permutations of a 2x3 board are accessible through moves of a subsquare, unlike the 3x3 case, where all 362880 permutations are accessible. They are:

123  156  245  324  412  456  534  623
456  342  163  516  653  123  126  541

124  162  246  325  413  461  536  624
365  354  315  461  526  325  241  153

125  163  251  326  415  462  541  625
643  245  364  145  362  531  623  314

126  164  253  341  416  463  542  631
534  523  146  265  235  152  361  524

132  165  254  342  421  465  543  632
546  432  613  156  563  213  216  451

134  213  256  345  423  512  546  634
652  465  431  612  615  436  132  215

135  214  261  346  425  513  561  635
264  356  453  521  136  642  234  142

136  215  263  351  426  514  562  641
425  634  514  426  351  263  143  352

142  216  264  352  431  516  563  642
635  543  135  641  256  324  421  513

143  231  265  354  432  521  564  643
562  645  341  162  165  346  312  125

145  234  312  356  435  523  612  645
326  561  564  214  621  164  345  231

146  235  314  361  436  524  613  651
253  416  625  542  512  631  254  243

152  236  315  362  451  526  614  652
463  154  246  415  632  413  532  134

153  241  316  364  452  531  615  653
624  536  452  251  316  462  423  412

154  243  321  365  453  532  621  654
236  651  654  124  261  614  435  321

It seems that every permutation of the top row is possible, but the permutation that that is determines the permutation of the bottom row.

The program follows. It's output file was then sorted and formatted for the above.

DECLARE FUNCTION permNo! (st$)
DECLARE SUB addMove ()
DECLARE FUNCTION fact! (x!)
DECLARE SUB move (seq$)

CLEAR , , 5000

DIM SHARED s$, sq$
startup:
s$ = "123456789"
CLS

DIM SHARED hist(720), histCt

sq$ = ""

hist(0) = 1: histCt = 1

OPEN "permrct.txt" FOR OUTPUT AS #2

addMove

CLOSE
FOR i = 0 TO 719: PRINT hist(i); : NEXT

SUB addMove
sqHold$ = sq$
IF LEN(sqHold$) = 0 THEN h$ = "b": ELSE h$ = LCASE$(RIGHT$(sqHold$, 1))
IF h$ = "b" THEN
   sq$ = sqHold$ + "a"
   s$ = "123456789"
   move sq$
   sbsc = permNo(MID$(s$, 1, 6))
   IF hist(sbsc) THEN
   ELSE
    hist(sbsc) = 1
    PRINT #2, MID$(s$, 1, 6), sq$
    addMove
   END IF
   sq$ = sqHold$ + "aa"
   s$ = "123456789"
   move sq$
   sbsc = permNo(MID$(s$, 1, 6))
   IF hist(sbsc) THEN
   ELSE
    hist(sbsc) = 1
    PRINT #2, MID$(s$, 1, 6), sq$
    addMove
   END IF
   sq$ = sqHold$ + "A"
   s$ = "123456789"
   move sq$
   sbsc = permNo(MID$(s$, 1, 6))
   IF hist(sbsc) THEN
   ELSE
    hist(sbsc) = 1
    PRINT #2, MID$(s$, 1, 6), sq$
    addMove
   END IF
END IF
IF LEN(sqHold$) = 0 OR h$ = "a" THEN
   sq$ = sqHold$ + "b"
   s$ = "123456789"
   move sq$
   sbsc = permNo(MID$(s$, 1, 6))
   IF hist(sbsc) THEN
   ELSE
    hist(sbsc) = 1
    PRINT #2, MID$(s$, 1, 6), sq$
    addMove
   END IF
   sq$ = sqHold$ + "bb"
   s$ = "123456789"
   move sq$
   sbsc = permNo(MID$(s$, 1, 6))
   IF hist(sbsc) THEN
   ELSE
    hist(sbsc) = 1
    PRINT #2, MID$(s$, 1, 6), sq$
    addMove
   END IF
   sq$ = sqHold$ + "B"
   s$ = "123456789"
   move sq$
   sbsc = permNo(MID$(s$, 1, 6))
   IF hist(sbsc) THEN
   ELSE
    hist(sbsc) = 1
    PRINT #2, MID$(s$, 1, 6), sq$
    addMove
   END IF
END IF

sq$ = sqHold$
END SUB

FUNCTION fact (n)
f = 1
FOR i = 1 TO n
f = f * i
NEXT
fact = f

END FUNCTION

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

FUNCTION permNo (st$)
tot = 0
FOR i = 1 TO LEN(st$) - 1
   t = 0
   FOR j = i + 1 TO LEN(st$)
     IF MID$(st$, j, 1) < MID$(st$, i, 1) THEN t = t + 1
   NEXT
   tot = tot + t * fact(LEN(st$) - i)
NEXT i
permNo = tot
END FUNCTION

Posted by Charlie on 2004-11-08 22:42:22

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:


perplexus dot info