ハノイの塔をプログラミングで解く

ハノイの塔とは一種のパズルで、ルールは以下のようです。

• 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
• 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
• 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

ハノイの塔 - Wikipedia

このルールの下で、左端に積み重ねられた円盤をすべて別のひとつの位置に移し替えるというものです。
　
再帰プログラミングでとても簡単に解けることを知りました。Ruby で解いてみます。

考え方はこうです。三つの場所を A, B, C とします。A に n 枚の円盤があるとき、

1. n - 1 枚の円盤を A から C に移します。
2. A に残った 1枚を B に移します。
3. n - 1 枚の円盤を C から B に移します。

ただし、n が 1 のときはただ A から B へ移せばよい。

これを素直にプログラミングするだけです。

def hanoi(n, from, to, via)
  if n == 1
    puts "#{from} から #{to} へ移す"
  else
    hanoi(n - 1, from, via, to)
    puts "#{from} から #{to} へ移す"
    hanoi(n - 1, via, to, from)
  end
end

hanoi(3, :A, :B, :C)

結果。円盤が 3枚の場合です。

A から B へ移す
A から C へ移す
B から C へ移す
A から B へ移す
C から A へ移す
C から B へ移す
A から B へ移す

これですべて A から B に移ります。特に n を大きくしてみると、こんな単純な再帰で解が求められるのが不思議な感じがします。
　
なお、これは以下の記事の LISP コードを Ruby に置き換えただけのことです。元記事に感謝します。