Rolling Cube 1の研究

 投稿者:GAI  投稿日:2009年10月12日(月)06時35分17秒
  ある方の研究によると、最初のさいころと空き地の初期設定は任意(さいころの目と向きは勝手に選べ、空き地も中央に限らずどこでもOK)
であったとしても、最低49手以内で最終形(上面に1の目が揃い、中央が空き地)に到達可能になるそうです。
そこで、初期条件を入力したら、最終形までの最短手順を見つけ出せるプログラムを作って頂けませんか?
以前、山中さんが掲載されていた1→2の経路探索プログラムをいじればいいような気もするのですが、まだ自分では手直し箇所がわかりませんのでよろしくお願いいたします。
 

Re: Rolling Cube 1の研究

 投稿者:山中和義  投稿日:2009年10月12日(月)09時17分1秒
  > No.630[元記事へ]

GAIさんへのお返事です。

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

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


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
LET SY=3 !空白の位置 ※番兵を考慮
LET SX=3

!●手数の上限を変更する場合

PUBLIC NUMERIC LIM !手数の上限 →最少手数
LET LIM=49 !←←←←← ※
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)
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 LET C=C+1 !1:目の数 ←←←←← ※
IF T2(3)<>1 THEN LET C=C+1
IF T3(3)<>1 THEN LET C=C+1
IF T4(3)<>1 THEN LET C=C+1
IF T5(3)<>1 THEN LET C=C+1
IF T6(3)<>1 THEN LET C=C+1
IF T7(3)<>1 THEN LET C=C+1
IF T8(3)<>1 THEN LET C=C+1
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 !上限までの手順
      SELECT CASE LVL(i)
      CASE 0
         PRINT "L"; !※さいころにとっては逆となる
      CASE 1
         PRINT "D";
      CASE 2
         PRINT "R";
      CASE 3
         PRINT "U";
      CASE ELSE
      END SELECT
   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)

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

!●さいころの目の配置(向き)を変更する場合

!展開図の配置と面番号(配列変数T1~T8の添え字に対応)との関係
! □    後    1
!□□□□ 左上右下 2345
! □    正    6
PUBLIC NUMERIC T1(6),T2(6),T3(6),T4(6),T5(6),T6(6),T7(6),T8(6) !8個のさいころ
DATA   5 !目の配置 ※展開図参照
DATA 4,1,3,6
DATA   2
MAT READ T1

DATA   5
DATA 4,6,3,1
DATA   2
MAT READ T2

DATA   5
DATA 4,1,3,6
DATA   2
MAT READ T3

DATA   5
DATA 4,6,3,1
DATA   2
MAT READ T4

DATA   5
DATA 4,6,3,1
DATA   2
MAT READ T5

DATA   5
DATA 4,1,3,6
DATA   2
MAT READ T6

DATA   5
DATA 4,6,3,1
DATA   2
MAT READ T7

DATA   5
DATA 4,1,3,6
DATA   2
MAT READ T8
PUBLIC SUB rolling
EXTERNAL SUB rolling(i,T()) !さいころを回転させる
   DIM TT(6) !作業用

   SELECT CASE i !※DX(),DY()参照
   CASE 0
      CALL PermMultiply(T,L,TT) !※さいころにとっては逆となる
   CASE 1
      CALL PermMultiply(T,D,TT)
   CASE 2
      CALL PermMultiply(T,R,TT)
   CASE 3
      CALL PermMultiply(T,U,TT)
   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
 

戻る