マクマホンのパズルへの応用

 投稿者:GAI  投稿日:2012年 2月 8日(水)17時59分30秒
  随分と昔に、こんなパズルは難し過ぎると思ったものにマクマホンのパズルと呼ばれるものに出会ったことがあり、解決には至らず、途中で投げ出したことを思い出しました。

(ルール)
マクマホンタイル
一辺が1の長さの正方形で、その対角線を引き4つの領域に分ける。各領域を重複を許し3色で塗り分けられる全タイル(24種類できる。)を用いて4×6の長方形に同じ色の辺が各行、各列で隣り合うように並べるパズル。
また、出来た長方形の周辺の色は同一色になっておくこと。


この解法に先程のアイデアが使えそうな感覚を持ちます。
もちろん私には、どこをどの様に変更すれば良いものなのか解らず、再び山中さんへプログラムの開発をお願いする次第です。
もし、決定的に異なるアルゴリズムでなければならないものなら、その点もよろしくお願いできますか?


 

Re: マクマホンのパズルへの応用

 投稿者:山中和義  投稿日:2012年 2月10日(金)18時51分14秒
  > No.1757[元記事へ]

GAIさんへのお返事です。

> マクマホンタイル

3^38通りの検証になりますので、PCでは不可能だと思います。
プログラムは掲載しますが、最初の1つの解でも実時間では何日かかるか解りません。


!マクマホン・タイル


!正方形の4辺を塗り分けたタイルを用い、同じ色の辺が隣り合うように並べる。
!3色24枚のセットを用い、辺の色が1色の長方形を作ることができる。

!以下の24種類
!1色系 A:0,1,2 ※0,1,2は色を表す
!1┌───┐
! │\A/│
! │A×A│
! │/A\│
! └───┘ 計3*1=3通り

!2色系 A:0,1,2、B:1,2,0
!1┌───┐ 2┌───┐ 3┌───┐ 4┌───┐
! │\A/│  │\A/│  │\A/│  │\A/│
! │B×A│  │B×A│  │B×B│  │B×B│
! │/A\│  │/B\│  │/A\│  │/B\│
! └───┘  └───┘  └───┘  └───┘ 計3*4=12通り

!3色系 A:0,1,2、B:1,2,0、C:2,0,1
!1┌───┐ 2┌───┐ 3┌───┐
! │\A/│  │\A/│  │\A/│
! │C×A│  │B×A│  │C×B│
! │/B\│  │/C\│  │/A\│
! └───┘  └───┘  └───┘ 計3*3=9通り

OPTION ARITHMETIC RATIONAL !多桁整数

LET t0=TIME

!題意を満たす色の並び
!┌───┐┌───┐┌───┐┌───┐┌───┐┌───┐
!│\0/││\0/││\0/││\0/││\0/││\0/│
!│0×1││1×2││2×3││3×4││4×5││5×0│
!│/6\││/7\││/8\││/9\││/A\││/B\│
!└───┘└───┘└───┘└───┘└───┘└───┘
!┌───┐┌───┐┌───┐┌───┐┌───┐┌───┐
!│\6/││\7/││\8/││\9/││\A/││\B/│
!│0×C││C×D││D×E││E×F││F×G││G×0│
!│/H\││/I\││/J\││/K\││/L\││/M\│
!└───┘└───┘└───┘└───┘└───┘└───┘
!┌───┐┌───┐┌───┐┌───┐┌───┐┌───┐
!│\H/││\I/││\J/││\K/││\L/││\M/│
!│0×N││N×O││O×P││P×Q││Q×R││R×0│
!│/S\││/T\││/U\││/V\││/W\││/X\│
!└───┘└───┘└───┘└───┘└───┘└───┘
!┌───┐┌───┐┌───┐┌───┐┌───┐┌───┐
!│\S/││\T/││\U/││\V/││\W/││\X/│
!│0×Y││Y×Z││Z×a││a×b││b×c││c×0│
!│/0\││/0\││/0\││/0\││/0\││/0\│
!└───┘└───┘└───┘└───┘└───┘└───┘

LET M=4 !m行n列
LET N=6
LET K=38 !0を0に固定して、1,2,3,…,Y,Z,a,b,c

DATA 0,0,1,6 !1
DATA 0,1,2,7 !2
DATA 0,2,3,8 !3
DATA 0,3,4,9 !4
DATA 0,4,5,A !5
DATA 0,5,0,B !6
DATA 6,0,C,H !7
DATA 7,C,D,I !8
DATA 8,D,E,J !9
DATA 9,E,F,K !10
DATA A,F,G,L !11
DATA B,G,0,M !12
DATA H,0,N,S !13
DATA I,N,O,T !14
DATA J,O,P,U !15
DATA K,P,Q,V !16
DATA L,Q,R,W !17
DATA M,R,0,X !18
DATA S,0,Y,0 !19
DATA T,Y,Z,0 !20
DATA U,Z,a,0 !21
DATA V,a,b,0 !22
DATA W,b,c,0 !23
DATA X,c,0,0 !24

DIM H(M*N,4) !4桁ずつmn個
FOR y=1 TO M*N !ピース番号を決めるパターンの桁の構成
   FOR x=1 TO 4
      READ d$
      LET H(y,x)=POS("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",d$)-1
   NEXT x
NEXT y
MAT PRINT H; !debug

PRINT 3^K !debug


LET C=0 !解の数

DIM B(0 TO K) !パターン
FOR i=0 TO 3^K-1 !0を0に固定して、1,2,3,…,Y,Z,a,b,cの計k個の変数は、0,1,2
   LET t=i
   FOR x=K TO 0 STEP -1 !3進法k桁へ
      LET B(x)=MOD(t,3)
      LET t=INT(t/3)
   NEXT x


   DIM F(0 TO 3^4-1) !ピースが重複するかどうか確認する
   MAT F=ZER
   FOR y=1 TO M*N !ピースの位置
      LET v0=B(H(y,1))*27+B(H(y,2))*9+B(H(y,3))*3+B(H(y,4)) !ピース番号 4桁ずつ
      LET v1=B(H(y,3))*27+B(H(y,1))*9+B(H(y,4))*3+B(H(y,2)) !90°回転
      LET v2=B(H(y,4))*27+B(H(y,3))*9+B(H(y,2))*3+B(H(y,1)) !180°回転
      LET v3=B(H(y,2))*27+B(H(y,4))*9+B(H(y,1))*3+B(H(y,3)) !270°回転
      LET t=MIN( MIN(v0,v1), MIN(v2,v3) ) !回転対称を除く

      IF F(t)=1 THEN EXIT FOR !重複!!!
      LET F(t)=1
   NEXT y
   IF y>M*N THEN !重複しないなら

      LET C=C+1 !結果を表示する
      PRINT "No.";C

      PRINT " +"; B(0); "+"; B(0); "+"; B(0); "+"; B(0); "+"; B(0); "+"; B(0); "+" !上端
      PRINT B(0); " "; B(1); " "; B(2); " "; B(3); " "; B(4); " "; B(5); " "; B(0); " " !1列目
      PRINT " +"; B(6); "+"; B(7); "+"; B(8); "+"; B(9); "+"; B(10); "+"; B(11); "+"
      PRINT B(0); " "; B(12); " "; B(13); " "; B(14); " "; B(15); " "; B(16); " "; B(0); " " !2列目
      PRINT " +"; B(17); "+"; B(18); "+"; B(19); "+"; B(20); "+"; B(21); "+"; B(22); "+"
      PRINT B(0); " "; B(23); " "; B(24); " "; B(25); " "; B(26); " "; B(27); " "; B(0); " " !3列目
      PRINT " +"; B(28); "+"; B(29); "+"; B(30); "+"; B(31); "+"; B(32); "+"; B(33); "+"
      PRINT B(0); " "; B(34); " "; B(35); " "; B(36); " "; B(37); " "; B(38); " "; B(0); " " !4列目
      PRINT " +"; B(0); "+"; B(0); "+"; B(0); "+"; B(0); "+"; B(0); "+"; B(0); "+" !下端

      PRINT

   END IF

NEXT i !次へ


PRINT "実行時間="; TIME-t0

END


実行結果

  :
  :

No. ?
+ 0 + 0 + 0 + 0 + 0 + 0 +
0   1   1   2   1   1   0
+ 0 + 0 + 2 + 2 + 1 + 2 +
0   1   2   1   1   1   0
+ 2 + 0 + 2 + 2 + 1 + 2 +
0   2   2   2   1   1   0
+ 0 + 0 + 2 + 1 + 2 + 1 +
0   0   2   2   1   1   0
+ 0 + 0 + 0 + 0 + 0 + 0 +

No. ?
+ 0 + 0 + 0 + 0 + 0 + 0 +
0   1   1   2   1   1   0
+ 0 + 0 + 2 + 2 + 1 + 2 +
0   1   2   1   1   1   0
+ 2 + 0 + 2 + 2 + 1 + 2 +
0   2   2   2   1   1   0
+ 2 + 0 + 2 + 1 + 2 + 1 +
0   0   0   2   1   1   0
+ 0 + 0 + 0 + 0 + 0 + 0 +

  :
  :

 

Re: マクマホンのパズルへの応用

 投稿者:山中和義  投稿日:2012年 2月15日(水)11時13分41秒
  > No.1758[元記事へ]

GAIさんへのお返事です。

> マクマホンタイル
>
> 3^38通りの検証になりますので、PCでは不可能だと思います。
> プログラムは掲載しますが、最初の1つの解でも実時間では何日かかるか解りません。

プログラムをバックトラック法に変更してみました。
PCに依りますが、1時間で40個程度、12時間で900個程度の解を見つけることができます。
12時間で、並びが、1,2,3,…,23,24から、1,2,22,21,…ですから全解を求めるのは困難です。

2進モードで実行してください。


!マクマホン(MacMahon)・タイル


!正方形の4辺を塗り分けたタイルを用い、同じ色の辺が隣り合うように並べる。
!3色24枚のセットを用い、辺の色が1色の長方形を作ることができる。

LET t0=TIME

!1つの解
! + 0 + 0 + 0 + 0 + 0 + 0 +
! 0   1   1   2   1   1   0
! + 0 + 0 + 2 + 2 + 1 + 2 +
! 0   1   2   1   1   1   0
! + 2 + 0 + 2 + 2 + 1 + 2 +
! 0   2   2   2   1   1   0
! + 0 + 0 + 2 + 1 + 2 + 1 +
! 0   0   2   2   1   1   0
! + 0 + 0 + 0 + 0 + 0 + 0 +
!より、

DATA 0,1,0,0 !1 ※時計の12時の位置から時計まわりに並べる
DATA 0,1,0,1 !2
DATA 0,2,2,1 !3
DATA 0,1,2,2 !4
DATA 0,1,1,1 !5
DATA 0,0,2,1 !6
DATA 0,1,2,0 !7
DATA 0,2,0,1 !8
DATA 2,1,2,2 !9
DATA 2,1,2,1 !10
DATA 1,1,1,1 !11
DATA 2,0,2,1 !12
DATA 2,2,0,0 !13
DATA 0,2,0,2 !14
DATA 2,2,2,2 !15
DATA 2,1,1,2 !16
DATA 1,1,2,1 !17
DATA 2,0,1,1 !18
DATA 0,0,0,0 !19
DATA 0,2,0,0 !20
DATA 2,2,0,2 !21
DATA 1,1,0,2 !22
DATA 2,1,0,1 !23
DATA 1,0,0,1 !24

PUBLIC NUMERIC M,N !盤の大きさ m行n列
LET M=4 !※固定
LET N=6


PUBLIC NUMERIC P(0 TO 23, 0 TO 3) !24枚のピース
MAT READ P

PUBLIC NUMERIC B(0 TO 23, 0 TO 3) !4行6列の盤

PUBLIC NUMERIC F(0 TO 23) !ピースの使用状況 0:未使用、1:使用
MAT F=ZER

PUBLIC NUMERIC C, cc !解の数
LET C=0

CALL try(0)

PRINT "実行時間=";TIME-t0

END


EXTERNAL SUB try(z) !バックトラック法で探索する
!枝刈り
!・右下に到達するまでに、4隅に入るピース(0が隣接する)を既に使い切ってしまった!
IF z>7 THEN
   IF F(0)>0 AND F(5)>0 AND F(6)>0 AND F(12)>0 AND F(18)>0 AND F(19)>0 AND F(23)>0 THEN EXIT SUB
END IF
!・中央部をすべて埋めて、中央に入るピース(0が1つもない)を使い切っていない!
IF z=(M-1)*N-1 AND ( F(8)=0 OR F(9)=0 OR F(10)=0 OR F(14)=0 OR F(15)=0 OR F(16)=0 ) THEN EXIT SUB


FOR i=0 TO M*N-1 !(mn)枚のピースを配置する。高々(mn)!通り
   IF F(i)=0 THEN !未使用なら
      LET F(i)=z+1 !使用中 ※0より大きな数


      DIM S(0 TO 3^4-1) !ピース番号
      MAT S=ZER
      FOR R=0 TO 3 !0°,90°,180°,270°回転して配置する
         LET t=0 !3進法4桁
         FOR j=0 TO 3
            LET v=P(i,MOD(j+R,4))
            LET t=t*3+v
            LET B(z,j)=v !z番目の位置にピースを置く(上書き)
         NEXT j
         IF S(t)=0 THEN !回転対称でないなら
            LET S(t)=1


            !---------- ↓↓↓↓↓ ----------
            !盤にピースが置けるかどうか確認する
            !  B(z-1,)   B(z,)=P(i,+R)
            !     0'       0
            !   3'  1'   3   1
            !     2'       2
            LET FLG=0

            IF z=0 THEN !左上隅(1番目)
               IF B(z,0)=0 THEN !上=色0
                  IF B(z,3)=0 THEN LET FLG=1 !左=色0
               END IF
            ELSEIF z=N-1 THEN !右上隅
               IF B(z,0)=0 THEN !上=色0
                  IF B(z-1,1)=B(z,3) THEN !左隣接1'=3
                     IF B(z-(N-1),3)=B(z,1) THEN LET FLG=1 !左端3'=右端1
                  END IF
               END IF
            ELSEIF z=(M-1)*N THEN !左下隅
               IF B(z,3)=0 THEN !左=色0
                  IF B(z-N,2)=B(z,0) THEN !上隣接2'=0
                     IF B(MOD(z,N),0)=B(z,2) THEN LET FLG=1 !上端0'=下端2
                  END IF
               END IF
            ELSEIF z=M*N-1 THEN !右下隅(最後)
               IF B(z-1,1)=B(z,3) THEN !左隣接1'=3
                  IF B(z-N,2)=B(z,0) THEN !上隣接2'=0
                     IF B(MOD(z,N),0)=B(z,2) THEN !上端0'=下端2
                        IF B(z-(N-1),3)=B(z,1) THEN LET FLG=1 !左端3'=右端1
                     END IF
                  END IF
               END IF

            ELSEIF z<N THEN !上端
               IF B(z,0)=0 THEN !上=色0
                  IF B(z-1,1)=B(z,3) THEN LET FLG=1 !左隣接1'=3
               END IF
            ELSEIF MOD(z,N)=0 THEN !左端
               IF B(z,3)=0 THEN !左=色0
                  IF B(z-N,2)=B(z,0) THEN LET FLG=1 !上隣接2'=0
               END IF
            ELSEIF MOD(z,N)=N-1 THEN !右端
               IF B(z-1,1)=B(z,3) THEN !左隣接1'=3
                  IF B(z-N,2)=B(z,0) THEN !上隣接2'=0
                     IF B(z-(N-1),3)=B(z,1) THEN LET FLG=1 !左端3'=右端1
                  END IF
               END IF
            ELSEIF z>=(M-1)*N THEN !下端
               IF B(z-1,1)=B(z,3) THEN !左隣接1'=3
                  IF B(z-N,2)=B(z,0) THEN !上隣接2'=0
                     IF B(MOD(z,N),0)=B(z,2) THEN LET FLG=1 !上端0'=下端2
                  END IF
               END IF

            ELSE !その他(中央部分)
               IF B(z-1,1)=B(z,3) THEN !左隣接1'=3
                  IF B(z-N,2)=B(z,0) THEN LET FLG=1 !上隣接2'=0
               END IF
            END IF
            !---------- ↑↑↑↑↑ ----------

            IF FLG=1 THEN !配置可能なら


               IF z=M*N-1 THEN !すべて揃ったなら
                  LET C=C+1 !結果を表示する
                  PRINT "No."; C
                  !!!MAT PRINT B; !debug

                  PRINT " +"; !上端
                  FOR x=0 TO N-1
                     PRINT B(x,0); "+";
                  NEXT x
                  PRINT
                  FOR y=0 TO M-1 !y行目
                     FOR x=0 TO N-1
                        PRINT B(y*N+x,3); " ";
                     NEXT x
                     PRINT B(y*N+N-1,1)

                     PRINT " +";
                     FOR x=0 TO N-1
                        PRINT B(y*N+x,2); "+";
                     NEXT x
                     PRINT
                  NEXT y


                  FOR y=1 TO M*N !ピース番号で並びを表示する
                     FOR x=0 TO M*N-1
                        IF F(x)=y THEN EXIT FOR
                     NEXT x
                     PRINT x+1;
                  NEXT y
                  PRINT


                    PRINT
               ELSE
                  CALL try(z+1) !次へ
               END IF


            END IF


         END IF
      NEXT R


      LET F(i)=0 !元に戻す
   END IF
NEXT i
END SUB

 

戻る