4ビットハノイの塔

「第参回天下一カウボーイ大会対談 古川享 x 遠藤諭 x 清水亮:魂を継ぐものたち」の中で、私が、4ビットマイコンの話をしています。その中で、以下のようなくだりがある。

遠藤 : これで「たまごっち」みたいにピーピー言ったら黙らせるプログラムとか、ハノイの塔とか書くわけです。
古川 : ハノイの塔できた?
清水 : どうやってやるのかわかんないですね。
遠藤 : 書きましたけど、それはこんどまたゆっくりと(笑)。

どちらかというとお二人の発言は、7個のLEDと1個の7セグLEDで、ハノイの塔をどうやって表現するんだ? というニュアンスかもしれませんが。4ビットマイコン版のハノイの塔は、以下のような仕様になっています。

a) 試せる板の枚数は2~13枚まで。
b) 動かす板を小さいほうから1~番号をふった数字(と音)で示す。
c) その板の動かし先をLEDの右3個を柱とみなし点灯する。

えっ、よく分からない? 下のYouTube動画を見てもらうとなんとなく分かるかもです。しかし、情報量的に俳句より大きく短歌より小さい宇宙でハノイの塔をプログラミングするとなるとそれなりに大変です(Prologとかで書くと信じられないほど短くなりますが)。Peter BunemanとLeon Levyという2人が、1980年代になって編み出したアルゴリズムを使っています。

何をやっているのかというと、まず、板の枚数をセット、次に、それぞれの板がどの棒にあるかのデータ(51h~)の内容を一応確認(上のビデオではすべての板が1の位置にある)。実行後は、すべての板が別の棒に移動しているかを確認しています(すべての板が4の位置に移っている)。

これは、実行中のウェイトやサウンドを外したバージョン。この4ビットマイコンでも目にも止まらぬ速さでハノイの塔7枚を解いてしまいます。いやー、コンピュータって速いんだなと改めて関心したりしてしまいます。ほとんど0.5秒くらいで終わってしまう。表示もしなかったらもっと速いでしょう。この4ビットマイコン結構速い?

// Tower of Hanoi for gmc-4 ver.2 
// 24/May/2009 / by © 2009 Satoshi Endo
//
00__A L00__TIY__1__1枚目から手をつける
01__1
02__5____MA
03__E____CALL__SHFT__1枚目はどんどん隣の柱に移す
04__6
05__F____JUMP__L09
06__0
07__A
08__8____TIA__4
09__4
0A__4 L09__AM____1枚目の新しい位置を記録
0B__3____CY
0C__E____CALL__SUND__1枚目の音を鳴らす
0D__B
0E__1____AO____1枚目を動かしたことを「1」と表示
0F__3____CY
10__A____TIY__E
11__E
12__4____AM
13__E____CALL__DSPR__1枚目をどの柱に送るかLEDで表現
14__D
15__8____TIA__5__表示後長さ「5」だけ休む
16__5________// ★休む長さを0~Fで指定★
17__E____CALL__TIMR
18__C
19__A____TIY__1
1A__1
1B__D L02__CIY__5__一番下の板まで処理したなら終わり
1C__5 L99______// ★板の枚数★
1D__F __JUMP__L05
1E__2
1F__5
20__E____CALL__ENDS
21__7
22__F L06__JUMP__L06__終了したら無限ループ
23__2
24__2
25__5 L05__MA____1枚目以外で動かせる
26__B __AIY__1__いちばん小さい板を求める
27__1________
28__7____M-
29__C____CIA__0__
2A__0
2B__F____JUMP__L01__動かせる板のとき
2C__3
2D__1
2E__F____JUMP__L02__
2F__1
30__B
31__5 L01__MA____板を動かす(算数力が問われる)
32__6____M+____例)2+2=4(いまの位置が2のとき)
33__7____M-______2–4=-2
34__4____AM
35__B____AIY__F____ 
36__F
37__5____MA______4(一つ上の板の位置が4だして)
38__B____AIY__1
39__1
3A__7____M-______-2–4=-6
3B__4____AM____
3C__8____TIA__7__
3D__7
3E__6____M+______ 7–6=1(7から引くと新しい位置)
3F__4 __AM____位置データ保存
40__3____CY
41__E____CALL__SUND__何枚目を動かすかを音で表現する
42__B
43__1____AO____何枚目の板か表示
44__3____CY
45__A____TIY__E
46__E
47__4____AM
48__E____CALL__DSPR__どの柱に送るかも表示
49__D
4A__8____TIA__5__表示後、長さ「5」だけ少し休む
4B__5________// ★休む時間を0~Fで指定★
4C__E____CALL__TIMR
4D__C
4E__F____JUMP__L00
4F__0
50__0
51 1 // 実行後に答えに書き換えられる
52 1 // 板は1~最大13枚まで使える(以下アドレスとの対応)。
53 1 // 
54 1 //_____|_ 板の番号__ |________|
55 1 //____ -_1_ 51h___ |________|
56 1 //____--_2_ 52h___|________|
57 1 //___ ---_3_ 53h__ |________|
58 1 //___----_4_ 54h__|________|
59 1 //__ -----_5_ 55h… |________|
5A 1 // ===========================
5B 1 // 4________ 2________ 1 
5C 1 //____ 柱の内部表現
5D 1 // 柱はLEDの右3個に対応して表示
5E 0 //___________________________ 
5F 0

// 以下プログラムのコード中を書き換えて調整する部分
16 5 表示の後の休む時間(0~F)
4B 5 表示の後に休む時間(0~F)
1C 5 板の枚数(板の枚数が5のとき。2~13を指定)

【実行するとどうなる】
移動すべき板の番号(数値)と移動先の柱位置(LED)を表示。
動かす板の番号を音程として鳴らす。
柱は、LEDのいちばん右側の3個で表現。

実行例)3枚(1Ch=3)で実行したときの表示結果と意味。
http://www.youtube.com/watch?v=UDqtWh_BqEU

【実行方法と結果確認】
板の枚数を L99(1Ch)の位置にセットする(上記ソースでは5)
実行後、51h~(枚数分)の中身の1だったのが、
すべて2、あるいはすべて4 となっていれば正しく動作した証拠。

Posted at 2009/07/27 14:48:58 by hortense