【Processing】ハノイの塔の視覚化をした

ハノイの塔とは
仕組み
ダウンロード

ハノイの塔とは

ハノイの塔は三本の柱と円盤から構成される塔で、常に小さいものが上に来るようにしながら、円盤を一枚ずつ移動させ。塔を他の柱に移すというものです。
単純な仕組みでありながら、円盤の数が増えると爆発的に作業量が増えるのが特徴です。
ja.wikipedia.org
この前、授業でも紹介されて、これを解くアルゴリズムがあることを知ったので視覚化してみました。

見にくいですが、とりあえず作業量がとても多いのは伝わるかと思います。

仕組み

以下のような再帰的関数で実装できます。
移動先(from)と移動元(to)に当たらない柱(other)を、再帰呼び出しの引数使用します。

void move(int no, int from, int to){//move disk from "from" stick to "to" stick
  int other = 3-from-to;//the other stick which is either of from stick and to stick.
  if(no > 1)move(no-1, from, other);
  steps.add(new Step(no, from, to));
  if(no > 1)move(no-1, other, to);
}