群論をゲームに

 投稿者:GAI  投稿日:2012年10月18日(木)17時34分24秒
  に面白いパズルを発見しました。

2つの操作(INVERT ,MARGE)があり

列:   1,2,3,4,5,6,7,8,9,10,11,12
に対し
INVERT→ 12,11,10,9,8,7,6,5,4,3,2,1
MARGE → 1,12,2,11,3,10,4,9,5,8,6,7 (綾織方式)
と変化させます。

初期条件をRANDOMIZEで作り、2つの操作を織り交ぜ最終的に番号順の
1,2,3,4,5,6,7,8,9,10,11,12
にして下さい。

どんな初期条件でも目的達成をさせるための戦略を練ってください。
これは互換と巡回を含む散在単純群(マシュー群M12)の構造と深く結びついているそうで
目的達成のためにはかなり長いステップを踏みます。

 

Re: 群論をゲームに

 投稿者:山中和義  投稿日:2012年10月20日(土)18時54分46秒
  > No.1991[元記事へ]

GAIさんへのお返事です。

> どんな初期条件でも目的達成をさせるための戦略を練ってください。

ルービックキューブのように順に揃えていく手法です。
6以降の置換がわかりませんので、12!通りすべてが整うことはありません。

DATA 12,11,9,6,7,10,1,2,4,5,8,3 など


!散在型単純群M12を表すマシューパズル


PUBLIC NUMERIC R(12),M(12) !置換を定義する
DATA 12,11,10,9,8,7,6,5,4,3,2,1 !Invert (1,12)(2,11)(3,10)(4,9)(5,8)(6,7)
DATA 1,12,2,11,3,10,4,9,5,8,6,7 !Merge (1)(2,3,5,9,8,10,6,11,4,7,12)
MAT READ R
MAT READ M

DIM T(12) !並び
DATA 3,7,6,5,9,8,1,2,4,12,11,10
MAT READ T
MAT PRINT T; !最初の並びを表示する

DIM TT(12)

PRINT "●1を揃える"
IF T(1)=1 THEN
   PRINT "1は揃っています。"
ELSE
   LET S=0
   DO UNTIL T(12)=1
      CALL PermMultiply(T,M,TT)
      MAT T=TT
      LET S=S+1
   LOOP
   CALL PermMultiply(T,R,TT)
   MAT T=TT
   IF S>1 THEN PRINT "M^";STR$(S); ELSE PRINT "M";
   PRINT "R"
   MAT PRINT T;
END IF


PRINT "●2を揃える"
IF T(2)=2 THEN
   PRINT "2は揃っています。"
ELSE
   LET S=0
   DO UNTIL T(2)=2
      CALL PermMultiply(T,M,TT)
      MAT T=TT
      LET S=S+1
   LOOP
   IF S>1 THEN PRINT "M^";STR$(S); ELSE PRINT "M";
   MAT PRINT T;
END IF


PRINT "●3を揃える"
LET x1$="RM^2RM^5RM^4" !X1=(1)(2)(8)(9)(3,10,4,5)(6,7,11,12)
LET x2$="RMRM^3RM^2" !X2=(1)(2)(4,9)(3,11,10,5,8,7,12,6)
IF T(3)=3 THEN
   PRINT "3は揃っています。"
ELSEIF T(4)=3 OR T(5)=3 OR T(10)=3 THEN
   CALL MOVE(3,3,T,x1$)
ELSEIF T(9)<>3 THEN
   CALL MOVE(3,3,T,x2$)
ELSE
   CALL MACRO(T,x2$) !9⇒4→3
   CALL MOVE(3,3,T,x1$)
END IF


PRINT "●4を揃える"
LET y1$="RM^3RMRM^3RMRM^2RM^3" !Y1=(1)(2)(3)(11)(4,7,6,12)(5,10,8,9)
LET y2$="MRMRMRM^4RM^2RMRMRM^6RM" !Y2=(1)(2)(3)(10)(4,7)(5,6)(8,12)(9,11)
IF T(4)=4 THEN
   PRINT "4は揃っています。"
ELSE
   IF T(6)=4 OR T(7)=4 OR T(12)=4 THEN
      CALL MOVE(4,4,T,y1$)
   ELSEIF T(11)=4 THEN
      CALL MACRO(T,y2$) !11⇒9→8⇒12→4
      CALL MOVE(4,8,T,y1$)
      CALL MACRO(T,y2$)
      CALL MOVE(4,4,T,y1$)
   ELSEIF T(5)=4 OR T(8)=4 OR T(9)=4 OR T(10)=4 THEN
      CALL MOVE(4,8,T,y1$) !→8⇒12→4
      CALL MACRO(T,y2$)
      CALL MOVE(4,4,T,y1$)
   END IF
END IF


PRINT "●5を揃える"
LET z1$="M^3RM^2RM^5RM" !Z1=(1)(2)(3)(4)(5,10,12,7)(6,8,11,9)
LET z2$="MRM^3RM^2RM^3RM^5R" !Z2=(1)(2)(3)(4)(5,6,12,11)(7,8,10,9)
IF T(5)=5 THEN
   PRINT "5は揃っています。"
ELSE
   IF T(7)=5 OR T(10)=5 OR T(12)=5 THEN
      CALL MOVE(5,5,T,z1$)
   ELSEIF T(6)=5 OR T(8)=5 OR T(9)=5 OR T(11)=5 THEN
      CALL MOVE(5,6,T,z1$) !→6→5
      CALL MOVE(5,5,T,z2$)
   END IF
END IF


PRINT "●6を揃える"
IF T(6)=6 THEN
   PRINT "6は揃っています。"
ELSE
   PRINT "未サポート"
   STOP
END IF


PRINT "●7を揃える"
IF T(7)=7 THEN
   PRINT "7は揃っています。"
ELSE
   PRINT "未サポート"
   STOP
END IF


PRINT "●8を揃える"
IF T(8)=8 THEN
   PRINT "8は揃っています。"
ELSE
   PRINT "未サポート"
   STOP
END IF


PRINT "●9を揃える"
IF T(9)=9 THEN
   PRINT "9は揃っています。"
ELSE
   PRINT "未サポート"
   STOP
END IF


PRINT "●10を揃える"
IF T(10)=10 THEN
   PRINT "10は揃っています。"
ELSE
   PRINT "未サポート"
   STOP
END IF


PRINT "●11,12を揃える"
IF T(11)=11 THEN
   PRINT "11,12は揃っています。"
ELSE
   PRINT "未サポート"
   STOP
END IF


PRINT "完成!"

END


EXTERNAL SUB MOVE(N,P,T(),S$) !数字nを位置pに移動させる
FOR i=1 TO 12
   IF T(P)=N THEN EXIT FOR !指定位置まで
   CALL MACRO(T,S$)
NEXT i
IF i>12 THEN !ループを確認する
   PRINT "並べ替えができません。"
   STOP
END IF
END SUB


EXTERNAL SUB MACRO(T(),S$) !マクロとして実行する
PRINT S$ !スクリプトを表示する

DIM TT(12)
LET i=1 !スクリプトを実行する
DO WHILE i<=LEN(S$)
   LET t$=UCASE$(S$(i:i)) !1文字コマンドとして
   SELECT CASE t$
   CASE "M"
      CALL PermMultiply(T,M,TT)
      MAT T=TT
      LET t0$="M"
   CASE "R"
      CALL PermMultiply(T,R,TT)
      MAT T=TT
      LET t0$="R"
   CASE "^" !べき乗
      LET i=i+1
      LET V=0 !数値を読み込む
      LET t$=UCASE$(S$(i:i))
      DO WHILE t$>="0" AND t$<="9" !10進法
         LET V=V*10+VAL(t$)
         LET i=i+1 !次の位へ
         LET t$=UCASE$(S$(i:i))
      LOOP
      LET i=i-1 !読み過ぎを戻す
      IF t0$="R" THEN
         FOR J=2 TO V !R^V
            CALL PermMultiply(T,R,TT)
            MAT T=TT
         NEXT J
      ELSE
         FOR J=2 TO V !M^V
            CALL PermMultiply(T,M,TT)
            MAT T=TT
         NEXT J
      END IF
   CASE " "
   !skip it
   CASE ELSE
      PRINT "文字列に誤りがあります。";i
      STOP
   END SELECT

   LET i=i+1 !次へ
LOOP

MAT PRINT T; !結果を表示する
END SUB



!置換(Permutation)の計算

EXTERNAL SUB PermIdentity(A()) !恒等置換
FOR i=1 TO UBOUND(A)
   LET A(i)=i
NEXT i
END SUB

EXTERNAL SUB PermInverse(A(), iA()) !逆置換 ※iAはA以外の配列を指定すること
FOR i=1 TO UBOUND(A)
   LET iA(A(i))=i
NEXT i
END SUB

EXTERNAL SUB PermMultiply(A(),B(), AB()) !積AB ※ABはA以外かつB以外の配列を指定すること
FOR i=1 TO UBOUND(A)
   LET AB(i)=A(B(i)) !※合成写像(AB)(i)=A(B(i))
NEXT i
END SUB


実行結果

3  7  6  5  9  8  1  2  4  12  11  10

●1を揃える
MR
1  8  2  9  4  5  12  6  11  7  10  3

●2を揃える
M^10
1  2  4  12  11  10  3  7  6  5  9  8

●3を揃える
RMRM^3RM^2
1  2  10  6  5  8  7  11  12  9  4  3

RMRM^3RM^2
1  2  8  12  9  3  11  5  6  4  10  7

RMRM^3RM^2
1  2  3  6  4  7  5  9  12  10  8  11

●4を揃える
RM^3RMRM^3RMRM^2RM^3
1  2  3  11  12  5  6  10  9  4  8  7

RM^3RMRM^3RMRM^2RM^3
1  2  3  7  9  6  11  4  10  12  8  5

MRMRMRM^4RM^2RMRMRM^6RM
1  2  3  11  6  9  7  5  8  12  10  4

RM^3RMRM^3RMRM^2RM^3
1  2  3  4  8  7  11  12  5  6  10  9

●5を揃える
M^3RM^2RM^5RM
1  2  3  4  11  5  9  7  10  8  12  6

MRM^3RM^2RM^3RM^5R
1  2  3  4  5  6  7  8  9  10  11  12

●6を揃える
6は揃っています。
●7を揃える
7は揃っています。
●8を揃える
8は揃っています。
●9を揃える
9は揃っています。
●10を揃える
10は揃っています。
●11,12を揃える
11,12は揃っています。
完成!

 

Re: 群論をゲームに

 投稿者:山中和義  投稿日:2012年10月21日(日)10時09分25秒
  > No.1992[元記事へ]

GAIさんへのお返事です。

> どんな初期条件でも目的達成をさせるための戦略を練ってください。

深さ優先検索(DFS)なら、最適解が見つかります。


!散在型単純群M12を表すマシューパズル

LET t0=TIME

DIM T(12) !並び
DATA 3,7,6,5,9,8,1,2,4,12,11,10
MAT READ T

PUBLIC NUMERIC MX !深さ
LET MX=100 !※調整が必要である

PUBLIC NUMERIC R(12),M(12) !置換を定義する
DATA 12,11,10,9,8,7,6,5,4,3,2,1 !Invert (1,12)(2,11)(3,10)(4,9)(5,8)(6,7)
DATA 1,12,2,11,3,10,4,9,5,8,6,7 !Merge (1)(2,3,5,9,8,10,6,11,4,7,12)
MAT READ R
MAT READ M

DIM Q(0 TO MX)
LET Q(0)=-1 !番兵
CALL try(1,Q,1,T)

PRINT "計算時間=";TIME-t0

END


EXTERNAL SUB try(P,Q(),D,T()) !バックトラック法で検証する
DIM TT(12)
FOR i=0 TO 1 !0:M、1:R
   IF Q(P-1)=i THEN LET DD=D+1 ELSE LET DD=1

   IF (DD=2 AND i=1) OR (DD=11 AND i=0) THEN !R^2=E, M^11=Eなので、連続させない
   ELSE
      IF i=0 THEN
         CALL PermMultiply(T,M,TT)
      ELSE
         CALL PermMultiply(T,R,TT)
      END IF
      LET Q(P)=i !p番目

      FOR J=1 TO 12 !揃ったかどうか確認する
         IF TT(J)<>J THEN EXIT FOR
      NEXT J
      IF J>12 THEN !揃ったなら
         PRINT P;":  "; !手

         LET V=Q(1) !スクリプトとして表示する
         LET W=1 !べき乗
         LET K=2 !文字位置
         DO WHILE K<=P
            IF Q(K)=V THEN !継続するなら
               LET W=W+1
            ELSE
               IF V=0 THEN PRINT "M"; ELSE PRINT "R"; !ここまでを切り出す
               IF W>1 THEN PRINT "^";STR$(W);
               LET V=Q(K)
               LET W=1
            END IF
            LET K=K+1 !次へ
         LOOP
         IF V=0 THEN PRINT "M"; ELSE PRINT "R"; !最後の文字列
         IF W>1 THEN PRINT "^";STR$(W);
         PRINT

         !!FOR K=1 TO P !debug
         !!   PRINT Q(K);
         !!NEXT K
         !!PRINT

         IF P<MX THEN LET MX=P !より最小のもの
      ELSE
         IF P<MX THEN CALL try(P+1,Q,DD,TT) !深さを制限して、次へ
      END IF
   END IF
NEXT i
END SUB



!置換(Permutation)の計算

EXTERNAL SUB PermIdentity(A()) !恒等置換
FOR i=1 TO UBOUND(A)
   LET A(i)=i
NEXT i
END SUB

EXTERNAL SUB PermMultiply(A(),B(), AB()) !積AB ※ABはA以外かつB以外の配列を指定すること
FOR i=1 TO UBOUND(A)
   LET AB(i)=A(B(i)) !※合成写像(AB)(i)=A(B(i))
NEXT i
END SUB

 

戻る