課題
ハノイの塔を解くためにはすでに用意してあるライブラリを利用します. 課題ではパズルの状態に応じて,画面を描画するコールバックを作成して下さい.
ハノイの塔
ハノイの塔とは,中心に孔の空いた円盤を棒に通して作られた塔を別の棒に移動させるパズルです.
上図では左の棒にあった塔を中央の棒に移したことを表しています. パズルでは円盤を移動するときには次のルールにしたがいます.
- 円盤を一度に一枚ずつ移動させる
- 積んである円盤のうち,最上段のものだけを移動できる
- 移動した円盤は必ずどれかの棒に通しておかなければならない
- ある円盤の上にそれより大きな円盤を載せることはできない(棒に何も積んでいないなら,どの円盤でも置くことができる)
なおどの二つの円盤も大きさは異なります.
テンプレート
次のテンプレートを使って下さい. このテンプレートでは描画コールバック(display)以外は完成しています.
テンプレートを実行して,[s]か[SPACE]を押すと,パズルを解き始めます. その過程で端末の画面にハノイの塔の情報が出るようになっています. なお2番目の例のように円盤の枚数を指定して実行することもできます. 指定しない場合は円盤は4枚です.
$ ruby hanoi.rb $ ruby hanoi.rb 6
ハノイの塔のデータ表現と描画
ハノイの塔を解く過程に現れる状態は3本の棒に積まれている円盤の列によって表せます. これをプログラムでは配列で表現できます. 円盤の枚数をNとします.円盤に小さい方から順に1,2,...,Nと番号をつけます. また3本の棒に左から順に0,1,2と番号をつけます.
このときたとえば次の図の状態を考えます.
- 左の棒(0)には下から5,2,1番の円盤がある
- 中央の棒(1)には円盤は一枚もない
- 右の棒(2)には下から4,3番の円盤がある
この状態を次の配列で表現できます.
towers = [[5,2,1],[],[4,3]]
towers[j]が左からj番めの棒にある円盤の列です.円盤を下から順に表しています. つまりtowers[j][i]が左からj番めの棒の下からi番めの円盤を表しています. なお下からi番めに円盤がない場合,towers[j][i]はnilです.
t=towers[0] # t = [5,2,1] t[0] # ==> 5 (towers[0][0]のこと) t=towers[1] # t = [] t[0] # ==> nil (towers[1][0]のこと.そのような円盤はない) t=towers[2] # t = [4,3] t[1] # ==> 3 (towers[2][1]のこと) t[2] # ==> nil (towers[2][2]のこと.そのような円盤はない)
ハノイの塔の状態(towers)が得られたら,その状態に合わせて,画面に円盤および棒を表示します. 各棒について下から何番目にどんな大きさの円盤を表示するかを塔の状態から適切に定めます. なお棒の長さと太さ,円盤の大きさ,色は適宜設定して構いません. 円盤の大きさは番号に基づいて算出するようにするとよいでしょう.
技術情報
プログラムで利用できるメソッドを示します.
# 配列.sizeで配列の要素数が得られる ary = [5,2,1] len = ary.size # ==> len == 3
サンプルプログラム
次にサンプルプログラムを示します.