LEDマトリクス版ハノイの塔 | Works ～作品集～ | Japanino特設サイト

「ハノイの塔」は簡単なルールのパズルゲームで、3本の柱のある台と何枚かの大きさの違う円盤を使います。まず、1本の柱に、円盤を大きい順に重ねます。そして、この円盤をすべて、別の柱に移します。

このとき、2つのルールがあります。

円盤は1度に1枚ずつ移動する。
小さい円盤の上に大きい円盤を重ねてはいけない。

Japaninoに3色LEDマトリクスパネルを接続し、このパズルを解くプログラムを動かしてみました。LEDマトリクスのモジュールは、16×16で、これを4個横に並べ、表示領域は64×16となっています。
制作：榊正憲

◆LEDマトリクスモジュール

ここで使ったLEDマトリクスのモジュールは、ドライバ/インターフェイス付きのものなので、トランジスタなどの外付け回路を用意することなく、プログラムでタイミング信号を制御しながら赤、緑のオン/オフデータをシリアル通信で送るだけで使用できます。ただし、LEDモジュール自体は、全LEDのデータを記することはできないので、常に表示のためにデータ出力を続けている必要があります。

ATMega168（8MHz）を使ったJapaninoでこの数のLEDを常時点灯させるのはタイミング的にはかなりきびしく、個々の信号線をdigitalWrite関数で制御したのでは間に合わず、表示がちらついてしまいます（digitalWrite関数は、内部でいろいろなチェックや操作を行っているので時間がかかるのです）。そこでこの例では、ポートに直接バイトデータを書き込むという、あまり好ましくないやり方でLEDパネルを制御しています（16MHzなら、digitalWrite関数でも、ほとんどちらつきのない表示が得られます）。

使用する円盤の数は1枚から10枚で、可変抵抗を使い、電圧変化をアナログポートで読み込んで枚数を決めています。最初はスイッチを押した回数で円盤の数を決めていたのですが、4個のモジュールすべてにデータ信号を送れるように配線した結果、スイッチ用のポートがなくなってしまったのです。

さて、肝心のハノイの塔のアルゴリズムですが、わずかこれだけです。

void hanoi(int src, int dst, int tmp, int cnt)
{
  if (cnt > 0) {
    hanoi(src, tmp, dst, cnt - 1);
    moveDisc(src, dst);
    hanoi(tmp, dst, src, cnt - 1);
  }
  return;
}

この関数には、元の柱、移動先の柱、もう1本の柱の番号と、移動する円盤の数を渡します。この関数の中で行っていることは簡単です。

指定した枚数より1枚少ない円盤をもう1本の柱に移す。
残った1枚の円盤を移動先の柱に移す。
もう1本の柱の円盤を移動先の柱に移す。

要点は、指定された枚数より1枚少ない円盤の移動のために、このhanoi関数自身を再び呼び出しているということです。このような呼び出しを、再帰呼び出しといいます。

だまされたような気がしますが、これでちゃんとパズルを解くことができるのです。例えば、3枚の円盤を移動するのであれば、最初に2枚を移動し、一番大きい1枚を移動先に移し、その上に先ほどの2枚を戻すということになります。この2枚の移動は、移動元、移動先、もう1本の柱の割り当てと円盤の枚数が異なる形で、同じ関数を呼び出しています。何度もこのような呼び出しを繰り返し、最後に1枚の移動になれば、普通に移動するだけです。

プログラミングの勉強では、再帰呼び出しの例としてハノイの塔の解法アルゴリズムがしばしば取り上げられています。

プログラムでは、ある柱から別の柱への円盤の移動をアニメーション表示するために、、上方向、水平方向、下方向に、1ドットずつ位置を変えながら表示しています。そして1ドット動かした後に表示ルーチンを呼び出しています（表示ルーチンの呼び出しが止まると、表示が消えてしまいます）。

LEDパネルは消費電力がかなり大きいので、Japanino側からは供給できないので、専用の電源を用意し駆動しています。作例では5V10A（50W）の電源を使用しています。Japaninoの基板は、作例ではUSB、あるいはバッテリーボックスから供給していますが、LED電源で駆動することもできます。別電源を使用する場合は、LED用電源とJapanino用電源の＋側を接続してはいけません（GNDどうしは接続しておく必要があります）。

◆使用したLEDマトリクスモジュールについて

参考までに、作例で使用したLEDマトリクスモジュールの使い方を簡単に説明しておきます。ほかの製品が同じ方法で使える訳ではありませんので、注意してください。また、ドライバ基板なしのLEDマトリクスは、使用方法がまったく異なります。

■形式: タキロン　DUG 80
■電源: LED 用　　　5V（専用の電源コネクタを使用）; 制御回路用　5V（信号コネクタのVcc端子）; 消費電流　　最大2.7A（LED用）

両方のコネクタに5Vを供給する必要があります。制御回路用は消費電力がわずかなので、Japanino側から供給しています。両方の電源のGND側を接続しておきます。

■入力コネクタ

ピン	名称
1	Vcc
2	Vcc
3	R:Sdata 　赤LEDデータ
4	G:Sdata 　緑LEDデータ
5	SClock　　データ伝送用クロック（立ち上がりでサンプル）
6	~Latch　　1行分のデータ伝送完了（行末尾データを送信した後にLOWパルス）
7	~Reset　　最上行に移動（最下行伝送中にLOWパルス）
8	Gnd
9	Gnd

■出力コネクタ

入力用と同じ形状の出力コネクタがあり、R:SdataとG:Sdata以外は、入力側の信号がそのまま出力されます。2つのSdata信号は、入力データをシフトレジスタで受けた後、桁あふれしたデータが出力されます。これにより、2個以上もモジュールをディジーチェーン接続することができます。1個のモジュールは16ドット幅ですが、2個接続すれば、32ドット幅として扱うことができます。

ただし幅を広くすると、データ伝送に要する時間が長くなりため、ダイナミック点灯の周期が長くなり、ちらつきが目立つ可能性があります。

作例では、2ユニットを接続して32×16ドットとし、それを2組使い、64×16としています。2つのSdata信号は個別にJapaninoから供給し、その他のタイミング信号は同じものを与えています。そのため、表示ルーチンでは、タイミング信号を1セット、データ信号を2セット出力しています。

■保護回路: タイミング制御がうまくいかず、特定の行のみが表示され続けると、熱の問題で素子が破損する可能性があるため、保護回路が組み込まれています。Latchパルスの間隔が2mS以上になると、LEDが消灯します。つまり、表示のためのタイミング信号の出力が止まってしまうと、LEDマトリクス全体が消灯してしまうということです。

本プログラムには、いかなる保証もありません。本プログラムは、自由に改変、再配布することができます。

2010年5月　榊　正憲

Hanoi.pde ［PDE:7KB］