|
|
ハノイの塔をバックトラック法により全探索します。
このプログラムでは普通のハノイの塔も求められますが、ここでは円盤4枚の4本ハノイの塔を求めてみました。
ネット上より入手した最少移動回数のデータを使用しています。
実行すると22通りもの解を得られました。下記の実行結果はその1解です。
棒3本では最少移動回数による解は1通りしかありませんが、4本以上になると自由度が増え複数の解が存在します。
該当する部分を注釈にするか削除する等すれば最少移動回数以外の解も表示します。
このプログラムでは枚数をNとすると、2^N進法を使って円盤の状態を記録します。
1枚目を2^0、2枚目を2^1、3枚目を2^2とし、N枚目を2^(N-1)とします。
そして一番右端(の棒)から左に向かって位が上がっていきます。
円盤4枚、棒4本の初期値は [15 0 0 0]でその意味は {2^4}^3*[2^3+2^2+2^1+2^0]+{2^4}^2*0+{2^4}^1*0+{2^4}^0*0で最大値になります。
これを[0 0 0 15]の最小値が目的の状態になります。{2^4}^3*0+{2^4}^2*0+{2^4}^1*0+{2^4}^0*[2^3+2^2+2^1+2^0]
このプログラムでは注意点があります。
もしも、"オーバーフローエラー"と表示されたら精度が不足しています。
1000桁モードや有理数モードを使用すれば解決しますが、ビット演算(BITAND 等)命令が53ビットまでしか対応していないので
必要なら自前で定義する必要があります。
また、棒の数が増えると組合せが膨大になり計算に時間がかかります。
全解ではなく1解でいい場合は表示後にSTOP文を入れてください。
http://oeis.org/A007664
http://oeis.org/A007665
https://oeis.org/search?q=Tower+of+Hanoi+with+6+pegs&sort=&language=&go=Search
PUBLIC NUMERIC NN,MM,LIMIT,PEG(0 TO 9),COUNT
PUBLIC STRING D$(200)
DIM S(0 TO 200) !'スタック(200回以上の場合は増やしてください)
!'''INPUT PROMPT "円盤の枚数=":NN
!'''INPUT PROMPT "棒の本数=":MM
LET NN=4 !' 円盤の枚数
LET MM=4 !' 棒の本数
SELECT CASE MM
CASE IS<=2
PRINT "解なし!"
STOP
CASE 3
RESTORE 3
CASE 4
RESTORE 4
CASE 5
RESTORE 5
CASE 6
RESTORE 6
CASE 7
RESTORE 7
CASE 8
RESTORE 8
CASE 9
RESTORE 9
CASE 10
RESTORE 10
CASE ELSE
RESTORE 100
END SELECT
FOR I=1 TO NN
READ LIMIT !'最少移動回数
IF LIMIT>2000 THEN EXIT FOR
NEXT I
LET PEG(MM-1)=2^NN-1
LET S(0)=STATUS(PEG) !'円盤の状態を 2^NN 進法で表し、配列Sに記録する
IF POS(STR$(S(0)),"E")>0 THEN
PRINT "オーバーフローエラー"
STOP
END IF
CALL HANOI(S,0,NN)
!' 以下はネット上より入手した最少移動回数データ
3 DATA 1, 3, 7, 15, 31, 63, 127, 100000000 ! 棒 3本時の最少移動回数 (8枚以上は無効)
4 DATA 1, 3, 5, 9, 13, 17, 25, 33, 41, 49, 65, 81, 97, 113, 129, 161, 193, 100000000 ! 棒 4本時の最少移動回数
5 DATA 1, 3, 5, 7, 11, 15, 19, 23, 27, 31, 39, 47, 55, 63, 71, 79, 87, 95, 103, 100000000! 棒 5本時の最少移動回数
6 DATA 1, 3, 5, 7, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 57, 65, 73, 81, 100000000 ! 棒 6本時の最少移動回数
7 DATA 1, 3, 5, 7, 9, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 100000000 ! 棒 7本時の最少移動回数
8 DATA 1, 3, 5, 7, 9, 11, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 100000000 ! 棒 8本時の最少移動回数
9 DATA 1, 3, 5, 7, 9, 11, 13, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 100000000 ! 棒 9本時の最少移動回数
10 DATA 1, 3, 5, 7, 9, 11, 13, 15, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 100000000 ! 棒 10本時の最少移動回数
100 DATA 100000000
END
EXTERNAL SUB HANOI(S(),SP,II)
IF SP>LIMIT THEN EXIT SUB !'最少移動回数を超えたら戻る(ここを外すと最少移動回数以外も探索します)
FOR I=0 TO SP-1
IF S(I)=S(SP) THEN EXIT SUB !'以前にあった状態と同じなら戻る
NEXT I
IF S(SP)=2^NN-1 THEN !'右端へ移動し終えたなら表示
LET COUNT=COUNT+1
PRINT COUNT;"解"
CALL DISPLAY(S,SP)
!''CALL DISPLAY2(D$,SP)
PRINT
PRINT " --- E N D ---"
PRINT
!'''STOP !!ここの注釈を外すと1解のみの表示になります。
EXIT SUB
END IF
CALL GETSTATUS(S(SP),PEG) !' 各棒の円盤の状態
FOR I=0 TO NN-1
IF I<>II THEN !'前回と違う円盤を移動させる
FOR J=MM-1 TO 0 STEP -1 !' I番目をJ から Kへ 左端の棒が MM-1 右端の棒が 0
LET TOP=BITAND(PEG(J),-PEG(J)) !'一番上の円盤
IF BITAND(PEG(J),2^I)>0 AND TOP=2^I THEN !'移動させる円盤がある棒
FOR K=0 TO MM-1
IF J<>K THEN !'移動元と移動先は違う棒
LET TOP=BITAND(PEG(K),-PEG(K)) !'一番上の円盤
IF (TOP>2^I OR TOP=0) AND BITAND(PEG(K),2^I)=0 THEN !'移動可能なら
LET PJ=PEG(J)
LET PEG(J)=BITXOR(PEG(J),2^I) !'棒J 上の円盤をリセット
LET PK=PEG(K)
LET PEG(K)=BITOR(PEG(K),2^I) !'棒K 上に円盤をセット
LET S(SP+1)=STATUS(PEG)
!''LET D$(SP+1)=STR$(I+1)&" 枚目を棒 "&MID$("ABCDEFGHIJ",MM-J,1)&" から棒 "&MID$("ABCDEFGHIJ",MM-K,1)&" へ"
CALL HANOI(S,SP+1,I) !'再帰呼出し(バックトラック法)
!''LET D$(SP+1)=""
LET PEG(J)=PJ
LET PEG(K)=PK
LET S(SP+1)=STATUS(PEG)
END IF
END IF
NEXT K
END IF
NEXT J
END IF
NEXT I
END SUB
EXTERNAL FUNCTION STATUS(PEG())
FOR I=MM-1 TO 0 STEP -1
LET SS=SS+(2^NN)^I*PEG(I)
NEXT I
LET STATUS=SS
END FUNCTION
EXTERNAL SUB GETSTATUS(N,PEG())
FOR I=MM-1 TO 0 STEP -1
LET PEG(I)=MOD(INT(N/(2^NN)^I),2^NN)
NEXT I
END SUB
EXTERNAL SUB DISPLAY(S(),SP)
DIM A$(NN)
FOR I=1 TO NN
LET A$(I)=REPEAT$(" ",2*NN-2*(I-1))&REPEAT$("■",2*I-1)&REPEAT$(" ",2*NN-2*(I-1))
NEXT I
FOR I=0 TO SP
PRINT REPEAT$("-",MM*(4*NN+2))
PRINT "No.";I
FOR J=0 TO NN-1
FOR K=MM-1 TO 0 STEP -1
LET L=MOD(INT(S(I)/(2^NN)^K),2^NN)
IF BITAND(L,2^J)>0 THEN
PRINT A$(J+1)
EXIT FOR
END IF
PRINT REPEAT$(" ",4*NN+2);
NEXT K
NEXT J
NEXT I
END SUB
EXTERNAL SUB DISPLAY2(D$(),SP)
FOR I=1 TO SP
PRINT "No.";I;" : ";D$(I)
NEXT I
END SUB
実行結果
1 解
------------------------------------------------------------------------
No. 0
■
■■■
■■■■■
■■■■■■■
------------------------------------------------------------------------
No. 1
■
■■■
■■■■■
■■■■■■■
------------------------------------------------------------------------
No. 2
■
■■■
■■■■■
■■■■■■■
------------------------------------------------------------------------
No. 3
■
■■■
■■■■■
■■■■■■■
------------------------------------------------------------------------
No. 4
■
■■■
■■■■■
■■■■■■■
------------------------------------------------------------------------
No. 5
■
■■■
■■■■■
■■■■■■■
------------------------------------------------------------------------
No. 6
■
■■■
■■■■■
■■■■■■■
------------------------------------------------------------------------
No. 7
■
■■■
■■■■■
■■■■■■■
------------------------------------------------------------------------
No. 8
■
■■■
■■■■■
■■■■■■■
------------------------------------------------------------------------
No. 9
■
■■■
■■■■■
■■■■■■■
--- E N D ---
以下略
|
|