ハノイの塔

私は突発的にGitHubにリポジトリを作っても最終的に消すことが度々あるため、自分のブログですらリンクを貼ることすらためらわれるのだが衝動的にハノイの塔のコードを書いた。

今回はCanvasとかではなく単純なHTMLとCSS、そしてJavaScriptだけで書いている。 昔も似たようなコードに挑戦したことはあるのだが、今回は最後まで書くことができた。

solveというボタンがあるのだが、このコードの生成はChatGPTに助けてもらった。 ボタンで操作できるようにはしているが、このボタンを押してハノイの塔の動かし方をビジュアルで確認できるようにした。 欲を言えば一時停止だったり、もとに戻したり、そういった機能も作れるのだけれども気が向いたら追加しようと思う。

function towerOfHanoi(n, source, auxiliary, target) {
  if (n === 1) {
    console.log(`Move disk 1 from ${source} to ${target}`);
    return;
  }

  towerOfHanoi(n - 1, source, target, auxiliary);
  console.log(`Move disk ${n} from ${source} to ${target}`);
  towerOfHanoi(n - 1, auxiliary, source, target);
}

ところで今回生成したコードだけれども、はっきり言ってこのコードを見ただけではなぜこのような動作をしてハノイの塔が実際に解けるのかよくわからない。 それくらい美しい再帰の表現なのかもしれないのだが、末尾再帰と違ってもはやこれが何を示しているのかこの投稿を書き始めた時点ではわからなかった。

ChatGPTが生成した解説はこうだ。

1. ディスクが1枚しかない場合（n === 1）、単に先頭のディスクをソースペグからターゲットペグに移動し、その移動を表示する。
2. そうでない場合は、再帰的戦略に従う：
   • 上位n-1個のディスクをソースペグから補助ペグに移動する。
   • 最大のディスク(ディスクn)をソースペグからターゲットペグに移動する。
   • ソースペグを補助として、n-1個のディスクを補助ペグからターゲットペグに移動する。

解説というよりもコードの中身をそのまま言い換えただけにしか聞こえない。

よくわからなかったし、せっかく生成したので試してみたいと思う。n = 3のときの出力は以下:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C <==
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

このときdisk 3をAからCまで動かした場合(<==の位置):

実はこの状態が重要で、3番目のディスクの存在を無視すればディスクが2枚のときと等価である。

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

n = 2にした出力結果は以下の3行だ。 この結果と見比べてみると、ペグの位置が異なるので出力は完全に一致するわけではないが、disk 1とdisk 2が移動して最終的にはdisk 1がCへ移動しているところは同じだ。

これはディスクが4枚であっても、あるいはそれ以上であっても同じことが言えるのでディスクの枚数を変えて試してみてほしい。 少々乱暴に聞こえるかもしれないが、ハノイの塔は理論上何枚のディスクが重なっていようと同様に必ず解くことできる。 これが数学的帰納法という説明である。

現実には最適化されていない再帰処理であることには変わりないのでnの数はその言語がサポートしているコールスタックの範囲でしか試すことしかできない。 ChatGPTで再帰ではなくループを使って書き直すように試してみたが、そのコードはうまく実行できなかった。

では再帰処理にそのものについても少し考えてみよう。

function towerOfHanoi(n, A, B, C) {
  console.log(`towerOfHanoi(${n}, ${A}, ${B}, ${C})`);

  if (n === 1) {
    console.log(`Move disk 1 from ${A} to ${C}`);
    return;
  }

  towerOfHanoi(n - 1, A, C, B);
  console.log(`Move disk ${n} from ${A} to ${C}`);
  towerOfHanoi(n - 1, B, A, C);
}

先頭にconsole.logを入れて、変数名をイメージしやすいように大文字に変更した:

towerOfHanoi(3, A, B, C)
towerOfHanoi(2, A, C, B)
towerOfHanoi(1, A, B, C)
Move disk 1 from A to C
Move disk 2 from A to B
towerOfHanoi(1, C, A, B)
Move disk 1 from C to B
Move disk 3 from A to C
towerOfHanoi(2, B, A, C)
towerOfHanoi(1, B, C, A)
Move disk 1 from B to A
Move disk 2 from B to C
towerOfHanoi(1, A, B, C)
Move disk 1 from A to C

いくら数学的に証明できるからといって、このコードはすぐに思い浮かぶものではない。 よくよく見るとn = 1までconsole.logが呼ばれるまではスタックに溜まっていることを確認できるし、Move disk 3が出力されている箇所がちょうど前処理と後処理に分かれているので興味深い。

実装しはじめた頃はここまでハノイの塔そのものを深堀りするつもりはなかったけれど、ハノイの塔のアルゴリズムとその解説がいまいち理解できなかったが、これでようやく理解できた。 文章だけでなく、インタラクティブに動かしてみることで初めて得られるものもあるのだろう。 最初に公開したときよりも大幅に書き換える結果となったけれども、満足できる投稿になった。