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