|
|
> No.630[元記事へ]
GAIさんへのお返事です。
サンプル・プログラム ※２進モードで実行してください。
!Rolling Cube 1 の解法
!●問題
!３×３の盤に、８個のさいころが１の目が上（他の目も同じ向き）で配置されています。
!空いているマスに転がして、すべての目が６になるようにしてください。
LET t0=TIME
PUBLIC NUMERIC xSIZE,ySIZE !盤の大きさ
LET xSIZE=3
LET ySIZE=3
!●さいころの盤上の配置を変更する場合
PUBLIC NUMERIC M(10,10) !さいころの配置 ※数字は番号、０は空き
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 !０手目
CALL backtrack(L,-1,SY,SX) !※番兵を考慮
PRINT "計算時間=";TIME-t0;"秒"
END
EXTERNAL SUB backtrack(L,D,SY,SX) !１手ずつ打っていき、行き詰まれば元に戻ってやり直す
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 !※「空き」を左下に位置付ける（３手以降） ←←←←← １つ下のIF文に置き換える
IF D>=0 THEN !２手以降
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 !※「空き」を左下に位置付ける ←←←←← １つ下の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の添え字に対応）との関係
! □ 後 １
!□□□□ 左上右下 ２３４５
! □ 正 ６
PUBLIC NUMERIC T1(6),T2(6),T3(6),T4(6),T5(6),T6(6),T7(6),T8(6) !８個のさいころ
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) !４近傍 ※反時計まわりの連番 右:0、上:1、左:2、下:3
DATA 1, 0,-1,0
DATA 0,-1, 0,1
MAT READ DX
MAT READ DY
END MODULE
|
|