1 [-|-] | | | [-|-] |
2 [--|--] | | -> | [--|--] |
3 [---|---] | | | [---|---] |
=====+=========+=========+====== =====+=========+=========+=====
A B C A B C
ゲームの目的は、円盤のスタックを、同じ順序のまま、棒「A」から棒「B」に移動
させることなのですが、その際、次の条件に従わなければなりません。
1) 円盤は一度に一枚づつ他の棒に移動させなければなりません。 2) 大きな円盤を小さな円盤の上に重ねてはなりません。つまり、「C」は一時的な退避場所として使われることになります。
このパズルは再帰的に解けるので、よく人工頭脳 (artificial interigence) の プログラムの例題に使われますが、Unix の sh を使うと、驚くべき短いステップ で解くことができます。例えば、次のスクリプト
if test $1 -lt 1; then exit 0; fi # 移動終り n=`expr $1 - 1` # 一つ前の円盤を move.cgi $n $2 $4 $3 # 一時退避させてから echo "円盤 $1 を $2 から $3 に移動" # その円盤を目的の場所に移動し move.cgi $n $4 $3 $2 # 退避させた円盤をその上に置くを「move」という名前にして、
$ move 3 A B Cと起動してみてください。「3 枚の円盤を A から B に移動し、C を退避場所に 使う」と言う意味です。たった、これだけで問題が解けます！
考え方はコメントとして書いて置きましたが、起動時の構文は、本来動かせない はずの、「一番下の円盤の移動を指示している」ことに注意してください。これ が「再帰処理」(recursive procedure) の素晴らしいところです。最後の処理だ け指示すれば、「その前にやらなければならないこと」は、再帰のメカニズムが 自動的に解決してくれます。
プログラムの中では、一番下から処理してゆくわけですから、まづ、一番上の処 理が終ったら、プログラムも終了するようにします。さもないと、永久に終りま せん。
後は、一つ前の円盤を一時退避させてから、その円盤を目的の場所に移動し、退 避させた円盤をその上に置くだけで、すべてが終ります！
位置パラメータ「$1」「$2」「$3」の意味は、次のように書き直すと、わかりや すくなります。
current=$1 # 移動対象 if test $current -lt 1; then exit 0; fi upper=`expr $current - 1` # 一つ上の円盤 FROM=$2 # 移動元 TO=$3 # 移動先 SPARE=$4 # 退避先 move $upper $FROM $SPARE $TO # 一つ上を退避 echo "円盤 $currnet を $FROM から $TO に移動" move $upper $SPARE $TO $FROM # 退避先から目的地に移動
このパズルの手続きは、円盤の枚数が増えるに従って、急速に増加します。例えば、 次のようなスクリプトを試してみると、増加の仕方がよくわかるでしょう。
for i in 1 2 3 4 5 6 7 8 9 10
do
echo "$i `move $i A B C | wc -l`"
done
ただし、あまりたくさん指定すると、メモリ不足になりますから、注意してくださ
い。
Unix のファイル・システムそのものが再帰的ですから、Unix の sh も再帰処理が 不可欠で、この機能がうまく生かせた例ですが、再帰というのは、その強力な能力 にもかかわらず、慣れないと考えにくいところがあるように思います。
平林 浩一