[課題05]: ハノイの塔

課題

パズル「ハノイの塔」を解く過程を順次表示するプログラムを作成して下さい．

課題のプログラムでハノイの塔のパズルを解く必要はありません．パズルを解く手順を計算して，(データとしての)円盤を順に移動させていくライブラリを用意してありますので，それを利用します．課題では，そのときどきの円盤の配置にしたがって，画面を描画するコールバックを作成して下さい．

なお円盤の枚数をNとして，Nが1以上のどんな整数であっても対応できるようなプログラムを作成してください．実際にはNが大きすぎる場合にはうまく表示できなくなりますが，プログラムがNの値に依存しないように記述されていれば問題ありません．

[2022-05-26] 更新情報

以下でテンプレートでの円盤の枚数のデータについての説明を追加しています．テンプレートでは「N」が円盤の枚数のデータを表しています．「DEFAULT_N」はプログラム実行時に円盤の枚数が指定されなかった場合の枚数です．更新前はこの点が不明確でした．

Nの値を使わなくてもプログラムは完成させられます．

ハノイの塔

ハノイの塔とは，中心に孔の空いた円盤を棒に通して作られた塔を別の棒に移動させるパズルです．

上図では左の棒にあった塔を中央の棒に移したことを表しています．パズルでは円盤を移動するときには次のルールにしたがいます．

円盤を一度に一枚ずつ移動させる
積んである円盤のうち，最上段のものだけを移動できる
移動した円盤は必ずどれかの棒に通しておかなければならない
ある円盤の上にそれより大きな円盤を載せることはできない(棒に何も積んでいないなら，どの円盤でも置くことができる)

なおどの2枚の円盤も大きさは異なります．同一の大きさの円盤は2枚以上ありません．

テンプレート

次のテンプレートを使って下さい．このテンプレートには描画コールバック(display)以外はすべて記述してあります．つまり描画コールバックだけが未完成の状態です．

hanoi_template.rb

テンプレートはそのまま実行できます．実行を開始した後，[s]か[SPACE]を押すと，パズルを解き始めて，解き終わるまで，自動的に処理を進めます．その過程で，端末(Terminal)の画面に各棒に積んである円盤の情報を順次表示するようになっています．

実行するときに，円盤の枚数を指定できます． 1番目の例では5枚と指定しています． 2番目の例のように枚数を指定しない場合，円盤は4枚になります．

  $ ruby hanoi.rb 5
  $ ruby hanoi.rb

枚数を多くするほど，手数が増えます．枚数を多くしすぎないようにしてください．

なおテンプレートではNの値が円盤の枚数となるように設定されます．上の最初の例の場合はN=5，2番目の例の場合はN=4となります．

アニメーションの実現方法

今回のプログラムにおいては，Keyboardコールバックで[s]か[SPACE]が押されたときに Idleコールバックを登録して，アニメーションを開始するようになっています．

Idleコールバックでは，1ステップ(円盤を1枚動かす)処理(__hanoi.step)を行って，パズルが解けたかどうかを判定して(__hanoi.complete?)，解き終わっていたら(つまり塔の移動が完了していたら)， (Idleコールバック内部で)Idleコールバックの登録を削除して，アニメーションを停止するようにしています．こうすることで，パズルを解き終えた時点でアニメーションを自動で停止できます．

ハノイの塔のデータ表現と描画

ハノイの塔を解く過程の状態は3本の棒に積まれている円盤の配置で表現されます．円盤の配置はプログラムでは配列で表現できます．円盤の枚数をNとします(テンプレートでは実際に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」です．「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

サンプルプログラム

次にサンプルプログラムを示します．