Rolling Cube 1

 投稿者:山中和義  投稿日:2009年 9月17日(木)10時17分17秒
  簡単なGUIのパズルゲームプログラミングです。
プログラムの中断は、「中断」ボタン(メニュー)で行います。
!●問題
!8個のさいころが、3×3の盤に1の目を上にして他の目も同じ向きで配置されています。
!空いているマスに転がして、すべての目が6になるようにしてください。


!置換(Permutation)の計算
SUB PermPrintOut(A()) !表示する
   MAT PRINT USING(REPEAT$(" ##",UBOUND(A))): A;
   PRINT
END SUB
SUB PermIdentity(A()) !恒等置換
   FOR i=1 TO UBOUND(A)
      LET A(i)=i
   NEXT i
END SUB
SUB PermInverse(A(), iA()) !逆置換 ※iAはA以外の配列を指定すること
   FOR i=1 TO UBOUND(A)
      LET iA(A(i))=i
   NEXT i
END SUB
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
!-------------------- ここまでがサブルーチン


DIM U(6),D(6),L(6),R(6) !置換
!    1,2,3,4,5,6
DATA 3,2,6,4,1,5 !上 ※正面を上面にするの(図での水平軸)回転
!!!DATA 5,2,1,4,6,3 !下
DATA 1,3,4,5,2,6 !左
!!!DATA 1,5,2,3,4,6 !右

MAT READ U
CALL PermInverse(U,D)
!!!MAT READ D
MAT READ L
CALL PermInverse(L,R)
!!!MAT READ R
!---------- ↑↑↑↑↑ ----------


!展開図の配置と面番号(配列の添え字)との関係
! □    後    1
!□□□□ 左上右下 2345
! □    正    6

DIM T1(6),T2(6),T3(6),T4(6),T5(6),T6(6),T7(6),T8(6) !8個のさいころ
DATA 5,4,1,3,6,2 !目の配置 ※展開図参照
MAT READ T1
MAT T2=T1 !同じ向き
MAT T3=T1
MAT T4=T1
MAT T5=T1
MAT T6=T1
MAT T7=T1
MAT T8=T1

PICTURE dice(T()) !さいころを表示する ※原点基準
   SET TEXT JUSTIFY "CENTER","HALF"
   PLOT TEXT ,AT 0,-0.4: STR$(T(1)) !側面の目の数
   PLOT TEXT ,AT -0.4,0: STR$(T(2))
   PLOT TEXT ,AT 0.4,0: STR$(T(4))
   PLOT TEXT ,AT 0,0.4: STR$(T(6))

   LET nm=T(3) !上面の目の数
   IF nm=1 THEN DRAW eye(4) !中央
   IF nm=3 OR nm=5 THEN DRAW eye(1)

   IF nm=2 OR nm=4 OR nm=5 OR nm=6 THEN !左斜め
      DRAW eye(1) WITH SHIFT(0.25,0.25)
      DRAW eye(1) WITH SHIFT(-0.25,-0.25)
   END IF
   IF nm=3 OR nm=4 OR nm=5 OR nm=6 THEN !右斜め
      DRAW eye(1) WITH SHIFT(0.25,-0.25)
      DRAW eye(1) WITH SHIFT(-0.25,0.25)
   END IF
   IF nm=6 THEN !中段
      DRAW eye(1) WITH SHIFT(0.25,0)
      DRAW eye(1) WITH SHIFT(-0.25,0)
   END IF
END PICTURE

PICTURE eye(c) !1つの目を表示する
   SET AREA COLOR c
   DRAW disk WITH SCALE(0.1) !※要調整
END PICTURE
!---------- ↑↑↑↑↑ ----------


LET MY=3 !マップの大きさ
LET MX=3

DIM M(MY,MX) !さいころの配置 ※数字は番号、0は空き
DATA 1,2,3
DATA 4,0,5
DATA 6,7,8
MAT READ M

SUB dispMap !マップ上のさいころを表示する
   FOR y=1 TO 3 !左上から順に
      LET yy=y-0.5 !位置を算出する
      FOR x=1 TO 3
         LET xx=x-0.5

         SELECT CASE M(y,x) !配置されたさいころに応じて
         CASE 1
            DRAW dice(T1) WITH SHIFT(xx,yy) !上面
         CASE 2
            DRAW dice(T2) WITH SHIFT(xx,yy)
         CASE 3
            DRAW dice(T3) WITH SHIFT(xx,yy)
         CASE 4
            DRAW dice(T4) WITH SHIFT(xx,yy)
         CASE 5
            DRAW dice(T5) WITH SHIFT(xx,yy)
         CASE 6
            DRAW dice(T6) WITH SHIFT(xx,yy)
         CASE 7
            DRAW dice(T7) WITH SHIFT(xx,yy)
         CASE 8
            DRAW dice(T8) WITH SHIFT(xx,yy)
         CASE ELSE
         END SELECT

      NEXT x
   NEXT y
END SUB
!---------- ↑↑↑↑↑ ----------


SUB move(T(),OP(),x,y,dx,dy) !さいころを回転移動させる
   LET ANSWER_COUNT=ANSWER_COUNT+1
   PRINT ANSWER_COUNT;"手"

   DIM TT(6) !作業配列
   CALL PermMultiply(T,OP,TT) !回転
   MAT T=TT
   LET w=M(y,x) !移動
   LET M(y,x)=M(y+dy,x+dx)
   LET M(y+dy,x+dx)=w
END SUB

SUB CalcDirection(x,y, T()) !移動可能な方向へ回転移動させる
   IF y>=2 THEN !上に移動可能で
      IF M(y-1,x)=0 THEN !空きマスなら
         CALL move(T,U,x,y,0,-1) !回転移動させる
         PRINT "UP";y;x
      END IF
   END IF
   IF y<=2 THEN !下
      IF M(y+1,x)=0 THEN
         CALL move(T,D,x,y,0,1)
         PRINT "DOWN";y;x
      END IF
   END IF
   IF x>=2 THEN !左
      IF M(y,x-1)=0 THEN
         CALL move(T,L,x,y,-1,0)
         PRINT "LEFT";y;x
      END IF
   END IF
   IF x<=2 THEN !右
      IF M(y,x+1)=0 THEN
         CALL move(T,R,x,y,1,0)
         PRINT "RIGHT";y;x
      END IF
   END IF
   MAT PRINT M; !debug
END SUB


LET ANSWER_COUNT=0 !手数

SET WINDOW -1,MX+1,MY+1,-1 !表示領域

LET cx=1 !ポインタを左上に位置付ける
LET cy=1
DO
   mouse poll x,y,left,right !マウスの情報を得る
   LET xx=INT(x) !位置
   LET yy=INT(y)
   IF xx>=0 AND xx<MX AND yy>=0 AND yy<MY THEN !マップ内なら
      LET cx=xx+1 ![1,MX]
      LET cy=yy+1 ![1,MY]
   END IF

   IF left=1 THEN !左ボタンが押されたら
      SELECT CASE M(cy,cx) !さいころの番号を得る
      CASE 1
         CALL CalcDirection(cx,cy, T1) !回転移動させる
      CASE 2
         CALL CalcDirection(cx,cy, T2)
      CASE 3
         CALL CalcDirection(cx,cy, T3)
      CASE 4
         CALL CalcDirection(cx,cy, T4)
      CASE 5
         CALL CalcDirection(cx,cy, T5)
      CASE 6
         CALL CalcDirection(cx,cy, T6)
      CASE 7
         CALL CalcDirection(cx,cy, T7)
      CASE 8
         CALL CalcDirection(cx,cy, T8)
      CASE ELSE
      END SELECT
      WAIT DELAY 0.2 !※要調整
   END IF

   SET DRAW mode hidden !ちらつき防止開始
   CLEAR
   DRAW grid !目盛り

   SET LINE width 2 !ポインタを表示する
   PLOT LINES: cx-1,cy-1; cx,cy-1; cx,cy; cx-1,cy; cx-1,cy-1
   SET LINE width 1

   CALL dispMap !さいころを表示する

   SET TEXT JUSTIFY "LEFT","BOTTOM" !文字位置の調整
   PLOT TEXT ,AT -0.5,-0.5: "移動するさいころを左クリックしてください。"

   SET DRAW mode explicit !ちらつき防止終了
LOOP


END


!答え 38手
! URDL,DRUL,LDRR,UULD,RUL;LDR,ULDD,RRUL,LDRU,LURD
 

Rolling Cube 1の拡張

 投稿者:GAI  投稿日:2009年 9月18日(金)14時47分11秒
  > No.556[元記事へ]

山中和義さんへのお返事です。

> 簡単なGUIのパズルゲームプログラミングです。
> プログラムの中断は、「中断」ボタン(メニュー)で行います。
>

> !●問題
> !8個のさいころが、3×3の盤に1の目を上にして他の目も同じ向きで配置されています。
> !空いているマスに転がしてすべての目が2、すべての目が3、すべての目が4、すべての目が5、すべての目が6になるようにしてください。

と問題を拡張することができますね。
それぞれの手順を発見してもらいたい。
 

Re: Rolling Cube 1の拡張

 投稿者:山中和義  投稿日:2009年 9月19日(土)11時06分0秒
  > No.557[元記事へ]

GAIさんへのお返事です。

> それぞれの手順を発見してもらいたい。

「将棋駒の入れ替え」同様 Give up です。

偶然に次のようなものが見つかれば、、、

1→5と1→4は、
1→2と1→3を見つけて、(何手かは不明)
2→5と3→4と考えて、1→6同様の反転で完成、ただし最少手とは限らない。

ところで、1→2などはみつかるのか?
1手に候補が平均3弱あるので、「場合の数」は、1→6と同じと考えても3^36程度。

・枝刈りとしては、回転や反転の対称を削除。(1手、2手を固定する)


ちなみに、1→6は URDL,LDRR,ULDL,URDR,ULDL,UURD,RULD,RDLU,LDRU (36手)。


このような問題は、『いかに「場合の数」を減らすのか』ということです。
覆面算やRolling Cube 2のような論理的、解析的な手法があればいいのですが、、、
 

Re: Rolling Cube 1の拡張

 投稿者:山中和義  投稿日:2009年 9月20日(日)08時45分23秒
  > No.558[元記事へ]

1→2
UR,DLLURRDLLURRDLLDRULDRULURDRULLDRRDLU;R,DLLUURRD,DLLUURRD,DLLUURRD,DLLU,R

セミコロンの前半(38手)
 222
 5 2
 222

セミコロンの後半(30手)
 xxx
 o x ○の反転
 xxx
 

Re: Rolling Cube 1の拡張

 投稿者:山中和義  投稿日:2009年 9月20日(日)12時35分26秒
  > No.560[元記事へ]

盤の対称性に気がつけば、、、

個々のさいころの向きは、

5   後   ※展開図、盤を上から見下ろしているので上面が見える
4136 左上右下
2   正

である。
前出の操作1→2は、正面(2の目)が上面に移動したことを意味する。

したがって、側面に着目すると
1→3は、盤の右(3の目)が下になるように盤を持ち替える。(時計まわりに90度回転)
その状態で、1→2の手順を行えばよい。

1→3
LU,RDDLUURDDLUURDDRULDRULDLURULDDRUURDL;U,RDDLLUUR,RDDLLUUR,RDDLLUUR,RDDL,U

※スクリプト記述は、盤が固定になるので、反時計まわりに90度回転になる。


1→4、1→5も同様。
 

Re: Rolling Cube 1の拡張

 投稿者:山中和義  投稿日:2009年10月 6日(火)11時56分22秒
  > No.562[元記事へ]

1→2の解法 WindowsMe、PentiumⅢ700MHz、192MBにて、十進BASIC 2進モードで実行。
 36 手
URDLURDDLURDLURDLULDRULDRURDLLUURRDL
-1 -1 -1 -1 -1
-1  3  5  2 -1
-1  6  0  8 -1
-1  1  7  4 -1
-1 -1 -1 -1 -1

  :省略
  :

計算時間= 5440.15 秒  ≒ 1.51 時間

サンプル・プログラム  ※2進モードで実行してください。
!Rolling Cube 1 の解法

!●問題
!3×3の盤に、8個のさいころが2の目が上(他の目も同じ向き)で配置されています。
!空いているマスに転がして、すべての目が1になるようにしてください。


LET t0=TIME


PUBLIC NUMERIC xSIZE,ySIZE !盤の大きさ
LET xSIZE=3
LET ySIZE=3

PUBLIC NUMERIC M(10,10) !さいころの配置 ※数字は番号、0は空き
MAT M=ZER(ySIZE+2,xSIZE+2)
DATA -1,-1,-1,-1,-1 !-1:壁 ※番兵
DATA -1, 1, 2, 3,-1 !←←←←← ※
DATA -1, 4, 0, 5,-1
DATA -1, 6, 7, 8,-1
DATA -1,-1,-1,-1,-1
MAT READ M

FOR SY=2 TO ySIZE+1 !空白の位置 ※番兵を考慮
   LET SX=2
   DO UNTIL SX=xSIZE+1
      IF M(SY,SX)=0 THEN EXIT FOR
      LET SX=SX+1
   LOOP
NEXT SY

PUBLIC NUMERIC LIM !手数の上限 →最少手数
LET LIM=36 !←←←←← ※

PUBLIC NUMERIC LVL(50) !手の記録
MAT LVL=ZER

LET L=0 !0手目
CALL backtrack(L,-1,SY,SX) !※番兵を考慮


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

END


EXTERNAL SUB backtrack(L,D,SY,SX) !1手ずつ打っていき、行き詰まれば元に戻ってやり直す

DECLARE EXTERNAL SUB Dice.rolling !外部手続き、変数の定義
DECLARE EXTERNAL NUMERIC Dice.T1(),Dice.T2(),Dice.T3(),Dice.T4()
DECLARE EXTERNAL NUMERIC Dice.T5(),Dice.T6(),Dice.T7(),Dice.T8()
DECLARE EXTERNAL NUMERIC Dice.DX(),Dice.DY()


DIM TT(6) !1つ前の保存
SUB ROTATEandMOVE(d) !さいころを回転移動する
   SELECT CASE id !回転
   CASE 1
      MAT TT=T1
      CALL rolling(d,T1)
   CASE 2
      MAT TT=T2
      CALL rolling(d,T2)
   CASE 3
      MAT TT=T3
      CALL rolling(d,T3)
   CASE 4
      MAT TT=T4
      CALL rolling(d,T4)
   CASE 5
      MAT TT=T5
      CALL rolling(d,T5)
   CASE 6
      MAT TT=T6
      CALL rolling(d,T6)
   CASE 7
      MAT TT=T7
      CALL rolling(d,T7)
   CASE 8
      MAT TT=T8
      CALL rolling(d,T8)
   CASE ELSE
   END SELECT

   LET M(SY,SX)=id !移動
   LET M(TY,TX)=0
END SUB
SUB RESTORE !元に戻す
   SELECT CASE id !回転
   CASE 1
      MAT T1=TT
   CASE 2
      MAT T2=TT
   CASE 3
      MAT T3=TT
   CASE 4
      MAT T4=TT
   CASE 5
      MAT T5=TT
   CASE 6
      MAT T6=TT
   CASE 7
      MAT T7=TT
   CASE 8
      MAT T8=TT
   CASE ELSE
   END SELECT

   LET M(TY,TX)=id !移動
   LET M(SY,SX)=0
END SUB


LET C=0 !枝刈り ※「残りの手数」と「目の数が一致しないさいころの数」との関係より
IF T1(3)<>1 THEN !1:目の数 ←←←←← ※
   IF T1(5)=1 THEN LET C=C+2 ELSE LET C=C+1
END IF
IF T2(3)<>1 THEN
   IF T2(5)=1 THEN LET C=C+2 ELSE LET C=C+1
END IF
IF T3(3)<>1 THEN
   IF T3(5)=1 THEN LET C=C+2 ELSE LET C=C+1
END IF
IF T4(3)<>1 THEN
   IF T4(5)=1 THEN LET C=C+2 ELSE LET C=C+1
END IF
IF T5(3)<>1 THEN
   IF T5(5)=1 THEN LET C=C+2 ELSE LET C=C+1
END IF
IF T6(3)<>1 THEN
   IF T6(5)=1 THEN LET C=C+2 ELSE LET C=C+1
END IF
IF T7(3)<>1 THEN
   IF T7(5)=1 THEN LET C=C+2 ELSE LET C=C+1
END IF
IF T8(3)<>1 THEN
   IF T8(5)=1 THEN LET C=C+2 ELSE LET C=C+1
END IF
!C個のさいころを一致させる必要があるが、残りの手数が足りないので、不可能!!!
IF L+C>LIM THEN EXIT SUB

IF C=0 AND M(3,3)=0 THEN !完成? ※「空き」が中央
!!!IF C=0 THEN !完成? ※「空き」が中央以外も含む
   PRINT L;"手"
   FOR i=1 TO L !上限までの手順
      LET w$="LDRU" !※さいころにとっては逆となる
      LET t=LVL(i)+1
      PRINT w$(t:t);
   NEXT i
   PRINT
   MAT PRINT M; !盤の状態

   !!  LET LIM=L !上限を狭める ←←←←← ※
END IF


IF L>=LIM THEN EXIT SUB !上限まで


!!!IF L>=2 THEN !※「空き」を左下に位置付ける(3手以降) ←←←←← 1つ下のIF文に置き換える
IF D>=0 THEN !2手以降
   FOR i=D-1 TO D+1 !逆行(後ろ)を避けて、(右・前・左へ)前進する
      LET DD=MOD(i,4) !連番で方向を得る
      LET TX=SX+DX(DD+1) !「空き」の進路位置
      LET TY=SY+DY(DD+1)
      LET id=M(TY,TX) !壁、さいころの番号を得る
      IF id>0 THEN !盤内なら
         CALL ROTATEandMOVE(DD) !さいころを転がす
         LET LVL(L+1)=DD !手を記録する
         CALL backtrack(L+1,DD,TY,TX) !次へ
         CALL RESTORE !元に戻す
      END IF
   NEXT i

ELSE
   FOR i=3 TO 0 STEP -1 !※「空き」を左下に位置付ける ←←←←← 1つ下のFOR文に置き換える(そのままでも可)
   !!!FOR i=0 TO 3 !全方向 ※連番
      LET TX=SX+DX(i+1) !「空き」の進路位置
      LET TY=SY+DY(i+1)
      LET id=M(TY,TX) !壁、さいころの番号を得る
      IF id>0 THEN !盤内なら
         CALL ROTATEandMOVE(i) !さいころを転がす
         LET LVL(L+1)=i !手を記録する
         CALL backtrack(L+1,i,TY,TX) !次へ
         CALL RESTORE !元に戻す
         !!!EXIT FOR !※「空き」を左下に位置付ける ←←←←← 削除する
      END IF
   NEXT i

END IF

END SUB


MODULE Dice !さいころを転がす

!置換(Permutation)の計算

SHARE NUMERIC U(6),D(6),L(6),R(6) !置換
!    1,2,3,4,5,6
DATA 3,2,6,4,1,5 !上 ※正面を上面にする(図での水平軸)回転
DATA 1,3,4,5,2,6 !左
MAT READ U
CALL PermInverse(U,D)
MAT READ L
CALL PermInverse(L,R)

SHARE NUMERIC UU(6,6),DD(6,6),LL(6,6),RR(6,6) !置換行列
CALL PermToMatrix(U,UU)
CALL PermToMatrix(D,DD)
CALL PermToMatrix(L,LL)
CALL PermToMatrix(R,RR)

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
EXTERNAL SUB PermToMatrix(A(), M(,)) !置換の行列を得る
   MAT M=ZER
   FOR i=1 TO UBOUND(A)
      LET M(i,A(i))=1
   NEXT i
END SUB
!---------- ↑↑↑↑↑ ----------


!展開図の配置と面番号(配列の添え字)との関係
! □    後    1
!□□□□ 左上右下 2345
! □    正    6

PUBLIC NUMERIC T1(6),T2(6),T3(6),T4(6),T5(6),T6(6),T7(6),T8(6) !8個のさいころ
DATA   1 !目の配置 ※展開図参照
DATA 4,2,3,5
DATA   6
MAT READ T1
MAT T2=T1 !同じ向き
MAT T3=T1
MAT T4=T1
MAT T5=T1
MAT T6=T1
MAT T7=T1
MAT T8=T1

PUBLIC SUB rolling
EXTERNAL SUB rolling(i,T()) !さいころを回転させる
!DIM TT(6) !作業用

   SELECT CASE i !※DX(),DY()参照
   CASE 0
   !CALL PermMultiply(T,L,TT) !※さいころにとっては逆となる
      MAT T=T*LL !※さいころにとっては逆となる
   CASE 1
   !CALL PermMultiply(T,D,TT)
      MAT T=T*DD
   CASE 2
   !CALL PermMultiply(T,R,TT)
      MAT T=T*RR
   CASE 3
   !CALL PermMultiply(T,U,TT)
      MAT T=T*UU
   CASE ELSE
   END SELECT

   !MAT T=TT
END SUB
!---------- ↑↑↑↑↑ ----------


PUBLIC NUMERIC DX(4),DY(4) !4近傍 ※反時計まわりの連番 右:0、上:1、左:2、下:3
DATA 1, 0,-1,0
DATA 0,-1, 0,1
MAT READ DX
MAT READ DY

END MODULE
 

戻る