第101回 プログラミングについて『ハノイの塔』

梵天が宇宙を創造したときに作った梵天の塔というものがインドにあるという。そこには６４枚の穴のあいた純金の円板が３本のダイアモンドの柱に通してある。円板の大きさはすべて異なり、最初１本目の柱に大きい順に通してあった。梵天は僧侶に、そのすべてを３本目の柱に移すことを命じた。しかし、円板は一度に一枚しか移動することとしか許さず、小さい円板の上に大きい円板を置くことは許さなかった。僧侶たちは休むことなく働いているが未だ終わる事はない。終わるときには世界は終末を迎える。

　といったことを本で読みました。ハノイの塔という言葉はどこかで聞いたことがあるような記憶はあるのですが、内容を知ったのはこれが初めてでした。多分ご存知の方も多いと思います。なかなか面白い話しで、ずっと頭に残っていました。暇なときなどに頭の中で円板を移動させて考えていたのですが、４枚くらい移動すると頭の中がごちゃごちゃになっていつもあきらめていました。そこで、これをプログラムにしてみようと思い立ったのです。

　プログラミングとしてはあまり参考にならないかも知れませんが、出来上がったものを眺めているのも結構楽しいものです。

ハノイの塔のアルゴリズムは既に何種類かが考えられていますが、ここではあまり難しいことを考えずにやってみます。

　まず、数値で考えてみましょう。考えやすくするために円板は３枚とし、下の図のようにします。

　1
　2
　3
　A B C

最初は 1 を移動しますが、B の柱か C の柱のどちらでも構いません。ここではすぐ隣の柱 B に移動します。

　2
　3 1
　A B C

次に移動できるのは 1 か 2 なのですが、2 を移動しましょう。2 は C の柱にしか移動できません。

　3 1 2
　A B C

次も 1 か 2 です。しかし 2 は A の柱に移動させると元に戻ってしまいますので、1をC に移動します。

　　　1
　3　 2
　A B C

次は 3 を B に移動します。

　　　1
　　3 2
　A B C

ここから先は図だけにします。

　　　　　　　　　　　　1
　　　　 →　 2　　→　 2　 →　 2　 →　　　 → 1　　 → 1　　 →
　1 3 2　　 1 3　　　　 3　　　　3 1　　2 3 1　　2 3　　　2　 3　　2 1 3
　A B C　　 A B C　　 A B C　　A B C　　A B C　　A B C　　A B C　　A B C

　　　　　　　　1
　　　2　→　　 2
　　1 3　　　　 3
　A B C　　 A B C

となり完成です。この動きには無駄がかなりありますが、とにかくこれでもいけそうですのでこの動きの約束事を文章にしましょう。

（１）動ける円板の中で最大のものを右に移動する。
（２）移動は最大柱２本分とし右に柱がないときには最も左の柱に戻る。
（３）移動によって直前のお状態には戻らない。
（４）３本目にすべてが移ったら終了。

約束事はこれだけです。要するに、同じ状態が２度ないように移動してすべてが３本目に移動したら終了するという考え方です。

　これをＤＯＳ版のプログラムにすることを考えましょう。いま円板の数がＮであったとき柱を、

　int pole[3][N];

として計算をする場合、円板を移動させるときに移動先の柱に円板があるかないかの判断をしなければならないことが予想されます（予想できますか？）。そうなるとプログラムがごちゃごちゃになってしまいますので、門番を一人加えて考えてみましょう。
　門番とは、Ｃ言語でいうと文字列（文字配列）の終端を示すヌルと同じもので、配列やリストの中（通常は最後）にデータとしてはありえない値を持つ要素のことを言います。そこで、円板の数がＮのときには、

　int pole[3][N+1];

として、すべての柱の一番下に円板の最大の大きさよりも大きい架空の円板を予め置いておくのです。そうすることで常に柱には円板が存在するので、円板があるか否かの判断をしなくてもいいことになります。この門番は結構使うテクニックですので覚えておいて下さい。

　次のプログラムが円板をセットしてその内容を表示するものです。

　#include <stdio.h>
　#include <string.h>

　#define MAX_RING　(3+1)

　main()
　{
　　int pole[3][MAX_RING];
　　int pole_top[3];
　　int i,j,k;

　　for(i=0;i<3;i++){
　　　if(i==0){　　　　　　　　　　　　　/* 一本目の柱 */
　　　　for(j=1;j<MAX_RING;j++)pole[i][j]=MAX_RING-j;
　　　}
　　　else{　　　　　　　　　　　　　　　/* 残りの柱 */
　　　　for(j=1;j<MAX_RING;j++)pole[i][j]=0;
　　　}

　　　pole[i][0]=MAX_RING;　　　　　　　 /* 門番 */
　　}

　　　　　　　　　　　　　　　　　　　　 /* 各柱の一番上の円板の要素を設定 */
　　pole_top[0]=MAX_RING-1;
　　pole_top[1]=0;
　　pole_top[2]=0;
　　　　　　　　　　　　　　　　　　　　 /* 表示 */
　　for(j=MAX_RING-1;j>=0;j--){
　　　printf("%2d %2d %2d\n",pole[0][j],pole[1][j],pole[2][j]);
　　}
　}

このプログラムでは円板の数を３とし、門番用に１つ多く配列を確保しています。
配列 pole_top は柱 pole の一番上の円板の位置の要素を示すための配列です。ここまでは難しくないと思います。これを実行してみると、

1　0　0
2　0　0
3　0　0
4　4　4

と表示されます。この結果の 4 が門番になります。

次は円板を移動させる機能を付けましょう。

　#include <stdio.h>
　#include <string.h>

　#define MAX_RING (3+1)

　void main()
　{
　　int　　 pole[3][MAX_RING];
　　int pole_top[3];
　　int　old_sts[2];　　　　　　　 /* 直前の状態を保持する配列 */
　　　　　　　　　　　　　　　　　 /* 要素０には円板のサイズ、
　　　　　　　　　　　　　　　　　　　要素１には柱の位置が入ります */

　　int　new_sts[3];　　　　　　　 /* 次の移動を計算するために使用する配列 */
　　　　　　　　　　　　　　　　　 /* 要素０には円板のサイズ、
　　　　　　　　　　　　　　　　　　　要素１には移動前の柱の位置
　　　　　　　　　　　　　　　　　　　要素２には移動後の柱の位置が入ります */
　　int i,j,k;

　　for(i=0;i<3;i++){
　　　if(i==0){
　　　　for(j=1;j<MAX_RING;j++)pole[i][j]=MAX_RING-j;
　　　}
　　　else{
　　　　for(j=1;j<MAX_RING;j++)pole[i][j]=0;
　　　}

　　　pole[i][0]=MAX_RING;
　　}

　　pole_top[0]=MAX_RING-1;
　　pole_top[1]=0;
　　pole_top[2]=0;

　　old_sts[0]= -1;　　　　　/* 直前の状態をありえない値で初期化 */

　　while(1){
　　　　　　　　　　　　　　 /* 現在の柱と円板の状態を表示 */
　　　for(j=MAX_RING-1;j>=0;j--){
　　　　printf("%2d %2d %2d\n",pole[0][j],pole[1][j],pole[2][j]);
　　　}

　　　getchar();　　　　　　 /* キー入力待ち */

　　　　　　　　　　　　　　 /* 柱１と柱２の円板の最上部が門番になったら完了 */
　　　if(pole_top[0]==0 && pole_top[1]==0)break;

　　　new_sts[0]= -1;　　　　/* 次の移動位置検索用の配列を初期化 */

　　　for(i=0;i<3;i++){　　　/* i は移動前の柱 */
　　　　for(j=1;j<3;j++){　　/* j は移動する柱の数 */
　　　　　k=(i+j)%3;　　　　 /* i+j が移動後の柱の位置ですが、 i+j が柱の数を
　　　　　　　　　　　　　　　　越えるときには最初の柱に循環させます */

　　　　　　　　　　　　　　 /* 円板の大きさを比較。移動先の円板の方が
　　　　　　　　　　　　　　　　小さいときには移動できません */
　　　　　if(pole[i][pole_top[i]]>=pole[k][pole_top[k]])continue;

　　　　　　　　　　　　　　 /* 移動できるときには、移動可能なものの中で最大の
　　　　　　　　　　　　　　　　円板であり、かつ前の状態にならないものを次に移
　　　　　　　　　　　　　　　　動する円板にします。*/

　　　　　if(new_sts[0]== -1 || new_sts[0]<pole[i][pole_top[i]]){
　　　　　　if(old_sts[0]!=pole[i][pole_top[i]] || old_sts[1]!=k){
　　　　　　　new_sts[0]=pole[i][pole_top[i]];
　　　　　　　new_sts[1]=i;
　　　　　　　new_sts[2]=k;
　　　　　　　break;
　　　　　　}
　　　　　}
　　　　}
　　　}

　　　　　　　　　　　　　　/* 移動する円板の現在の状態を old_sts に保存 */

　　　old_sts[0]=pole[new_sts[1]][pole_top[new_sts[1]]];
　　　old_sts[1]=new_sts[1];

　　　　　　　　　　　　　　/* 円板を移動させます */
　　　pole_top[new_sts[2]]++;
　　　pole[new_sts[2]][pole_top[new_sts[2]]]=
　　　　　　　　　　　　　　　　　　　　 pole[new_sts[1]][pole_top[new_sts[1]]];

　　　pole[new_sts[1]][pole_top[new_sts[1]]]=0;

　　　pole_top[new_sts[1]]--;
　　}
　}

このプログラムを実行し、順次リターンキーを押せば次々と数字が移動していき最後にすべて３番目の柱に移動します。 MAX_RING の値をもう少し大きくして試してみて下さい。ただ６以上になるとリターンキーを押すのが辛くなった上、何をやっているのかが分からなくなってしまいますので注意して下さい。

次にＷｉｎｄｏｗｓ版のものを載せましたので楽しんでみて下さい。内容はこれまでに説明してきたものですので特には説明しません。

　#include <afxwin.h>
　#include "dummy.h"

　#define MAX_RING　　　　　(10+1)

　#define RING_DELTA_RADIUS 3
　#define RING_THICK　　　　5
　#define RING_GAP　　　　　2

　#define POLE_RADIUS　　　 5
　#define POLE_HEIGHT　　　 ((RING_THICK+RING_GAP)*MAX_RING-RING_GAP)

　#define　　TOP_MARGIN　　 (RING_THICK*3)
　#define BOTTOM_MARGIN　　 10

　#define WINDOW_XSIZE　　　((POLE_RADIUS*2+RING_DELTA_RADIUS*2*MAX_RING+50)*3)
　#define WINDOW_YSIZE　　　(POLE_HEIGHT+TOP_MARGIN+BOTTOM_MARGIN)

　#define ID_PLAY　　　　　 100
　#define ID_IDLE　　　　　 101

　#define BLCACK　　　　　　　RGB(　0,　0,　0)
　#define RED　　　　　　　　 RGB(255,　0,　0)
　#define GREEN　　　　　　　 RGB(　0,255,　0)
　#define BLUE　　　　　　　　RGB(　0,　0,255)
　#define CYAN　　　　　　　　RGB(　0,255,255)
　#define YELLOW　　　　　　　RGB(255,255,　0)
　#define MAGENTA　　　　　　 RGB(255,　0,255)
　#define WHITE　　　　　　　 RGB(255,255,255)
　#define DBLACK　　　　　　　RGB(　0,　0,　0)
　#define DRED　　　　　　　　RGB(128,　0,　0)
　#define DGREEN　　　　　　　RGB(　0,128,　0)
　#define DBLUE　　　　　　　 RGB(　0,　0,128)
　#define DCYAN　　　　　　　 RGB(　0,128,128)
　#define DYELLOW　　　　　　 RGB(128,128,　0)
　#define DMAGENTA　　　　　　RGB(128,　0,128)
　#define DWHITE　　　　　　　RGB(128,128,128)
　#define MWHITE　　　　　　　RGB(192,192,192)

　#define POLE_COLOR　　　　　WHITE
　#define RING_COLOR　　　　　YELLOW
　#define RING_FROM_COLOR　　 RED
　#define RING_TO_COLOR　　　 DYELLOW
　#define BACK_COLOR　　　　　MWHITE

　#define INTERVAL　　　　　　1000

　#define WRITE_MODE_ERASE　　0
　#define WRITE_MODE_NORMAL　 1
　#define WRITE_MODE_FROM　　 2
　#define WRITE_MODE_TO　　　 3

　/*============================== Class HanoiApp =============================
　* Class HanoiApp.
　*/
　class HanoiApp : public CWinApp
　{
　　private:
　　　virtual BOOL OnIdle(LONG lCount);

　　public:
　　　virtual BOOL InitInstance();
　};

　/*=============================== Class Hanoi ===============================
　* Class Hanoi.
　*/
　class Hanoi : public CFrameWnd
　{
　　private:
　　　int playing;

　　　DWORD old_time;

　　　int pole　　[3][MAX_RING];
　　　int pole_top[3];
　　　int old_sts [2];

　　　afx_msg void OnPaint();
　　　afx_msg void OnIdle();

　　　　　　　void Redraw(int write_mode,int wpole= -1,int wring= -1);
　　　　　　　void Delay(double delta_time);
　　　　　　　CPen　 *SetPen　(CDC *dc,CPen　 *pen　,COLORREF color);
　　　　　　　CBrush *SetBrush(CDC *dc,CBrush *brush,COLORREF color);
　　　　　　　void　UnsetPen　(CDC *dc,CPen　 *pen　,CPen　 *old_pen　);
　　　　　　　void　UnsetBrush(CDC *dc,CBrush *brush,CBrush *old_brush);

　　public:
　　　Hanoi();

　　　DECLARE_MESSAGE_MAP()
　};

　/*============================== Make HanoiApp ==============================
　* Make HanoiApp.
　*/
　class HanoiApp HanoiApp;

　/*========================== HanoiApp::InitInstance =========================
　* HanoiApp::InitInstance.
　*/
　BOOL HanoiApp::InitInstance()
　{
　　m_pMainWnd = new class Hanoi;

　　return TRUE;
　}
　/*============================= hanoiApp::OnIdle ============================
　* HanoiApp::OnIdle.
　*/
　BOOL HanoiApp::OnIdle(LONG lCount)
　{
　　m_pMainWnd->PostMessage(WM_COMMAND,ID_IDLE);

　　return TRUE;
　}

　/*=============================== Hanoi::Hanoi ==============================
　* Hanoi::Hanoi.
　*/
　Hanoi::Hanoi()
　{
　　RECT rect;
　　int　xsize,ysize;
　　int　i,j;
　/*
　* " Create "
　*/
　　Create(
　　　(const char *)AfxRegisterWndClass(
　　　　　　　　　　　CS_HREDRAW | CS_VREDRAW,
　　　　　　　　　　　LoadCursor(NULL,IDC_ARROW),
　　　　　　　　　　　(HBRUSH)(COLOR_WINDOW)),
　　　"Hanoi",
　　　WS_BORDER | WS_CAPTION | WS_OVERLAPPED | WS_MINIMIZEBOX | WS_SYSMENU,
　　　rectDefault);
　/*
　* " Set window size and position "
　*/
　　GetWindowRect(&rect);
　　xsize=rect.right -rect.left;
　　ysize=rect.bottom-rect.top ;

　　GetClientRect(&rect);
　　xsize-=(rect.right -rect.left);
　　ysize-=(rect.bottom-rect.top );

　　xsize+=WINDOW_XSIZE;
　　ysize+=WINDOW_YSIZE;

　　SystemParametersInfo(SPI_GETWORKAREA,0,&rect,0);

　　MoveWindow(
　　　(rect.left+rect.right )/2-xsize/2,
　　　(rect.top +rect.bottom)/2-ysize/2,
　　　xsize,ysize);

　　ShowWindow(SW_SHOW);
　/*
　* " Initialize data members "
　*/
　　for(i=0;i<3;i++){
　　　if(i==0){
　　　　for(j=1;j<MAX_RING;j++)pole[i][j]=MAX_RING-j;
　　　}
　　　else{
　　　　for(j=1;j<MAX_RING;j++)pole[i][j]=0;
　　　}

　　　pole[i][0]=MAX_RING;
　　}

　　pole_top[0]=MAX_RING-1;
　　pole_top[1]=0;
　　pole_top[2]=0;

　　old_sts[0]= -1;

　　playing=0;

　　old_time=0;
　}
　/*============================== Hanoi::OnPaint =============================
　* Hanoi::OnPaint.
　*/
　afx_msg void Hanoi::OnPaint()
　{
　　CPaintDC dc(this);

　　Redraw(WRITE_MODE_NORMAL);

　　if(!playing){
　　　playing=1;

　　　if(MessageBox("開始しますか？","開始",MB_YESNO)==IDNO){
　　　　PostQuitMessage(0);
　　　　return;
　　　}
　　　else{
　　　　PostMessage(WM_COMMAND,ID_PLAY);
　　　}
　　}
　}
　/*=============================== Hanoi::Delay ==============================
　* Hanoi::Delay.
　*/
　void Hanoi::Delay(double delta_time)
　{
　　DWORD to,dt;

　　dt=(int)(delta_time*1000.0);

　　to=GetTickCount();

　　while(1){
　　　if(GetTickCount()-to>dt)break;
　　}
　}
　/*============================== Hanoi::SetPen ==============================
　* Hanoi::SetPen.
　*/
　CPen *Hanoi::SetPen(CDC *dc,CPen *pen,COLORREF color)
　{
　　pen->CreatePen(PS_SOLID,0,color);
　　return dc->SelectObject(pen);
　}
　/*============================= Hanoi::SetBrush =============================
　* Hanoi::SetBrush.
　*/
　CBrush *Hanoi::SetBrush(CDC *dc,CBrush *brush,COLORREF color)
　{
　　brush->CreateSolidBrush(color);
　　return dc->SelectObject(brush);
　}
　/*============================= Hanoi::UnsetPen =============================
　* Hanoi::UnsetPen.
　*/
　void Hanoi::UnsetPen(CDC *dc,CPen *pen,CPen *old_pen)
　{
　　dc->SelectObject(old_pen);
　　pen->DeleteObject();
　}
　/*============================ Hanoi::UnsetBrush ============================
　* Hanoi::UnsetBrush.
　*/
　void Hanoi::UnsetBrush(CDC *dc,CBrush *brush,CBrush *old_brush)
　{
　　dc->SelectObject(old_brush);
　　brush->DeleteObject();
　}
　/*============================== Hanoi::OnIdle ==============================
　* Hanoi::OnIdle.
　*/
　afx_msg void Hanoi::OnIdle()
　{
　　DWORD cur_time;
　　int　 new_sts[3];
　　int　 i,j,k;

　　if(!playing)return;

　　cur_time=GetTickCount();
　　if(cur_time-old_time<=INTERVAL)return;

　　new_sts[0]= -1;

　　for(i=0;i<3;i++){
　　　for(j=1;j<3;j++){
　　　　k=(i+j)%3;

　　　　if(pole[i][pole_top[i]]>=pole[k][pole_top[k]])continue;

　　　　if(new_sts[0]== -1 || new_sts[0]<pole[i][pole_top[i]]){
　　　　　if(old_sts[0]!=pole[i][pole_top[i]] || old_sts[1]!=k){
　　　　　　new_sts[0]=pole[i][pole_top[i]];
　　　　　　new_sts[1]=i;
　　　　　　new_sts[2]=k;
　　　　　　break;
　　　　　}
　　　　}
　　　}
　　}

　　Redraw(WRITE_MODE_FROM,new_sts[1],pole_top[new_sts[1]]);
　　Delay(0.5);
　　Redraw(WRITE_MODE_ERASE,new_sts[1],pole_top[new_sts[1]]);

　　old_sts[0]=pole[new_sts[1]][pole_top[new_sts[1]]];
　　old_sts[1]=new_sts[1];

　　pole_top[new_sts[2]]++;
　　pole[new_sts[2]][pole_top[new_sts[2]]]=
　　　　　　　　　　　　　　　　　　　pole[new_sts[1]][pole_top[new_sts[1]]];

　　pole[new_sts[1]][pole_top[new_sts[1]]]=0;

　　pole_top[new_sts[1]]--;

　　Redraw(WRITE_MODE_TO,new_sts[2],pole_top[new_sts[2]]);
　　Delay(0.5);
　　Redraw(WRITE_MODE_NORMAL,new_sts[2],pole_top[new_sts[2]]);

　　if(pole_top[0]==0 && pole_top[1]==0){
　　　MessageBox("終了しました","終了",MB_OK);
　　　PostQuitMessage(0);
　　}

　　old_time=GetTickCount();
　}
　/*============================== Hanoi::Redraw ==============================
　* Hanoi::Redraw.
　*/
　void Hanoi::Redraw(int write_mode,int wpole,int wring)
　{
　　CClientDC dc(this);

　　CPen　 pen　,*old_pen　;
　　CBrush brush,*old_brush;

　　COLORREF color;

　　int npole,nring,x,y,xsize;
　/*
　* " Write all "
　*/
　　if(wpole== -1){
　　　　　　　　　　　　　　　　　　　　　　　　　　　// Write pole.
　　　old_pen　=SetPen　(&dc,&pen　,POLE_COLOR);
　　　old_brush=SetBrush(&dc,&brush,POLE_COLOR);

　　　for(npole=0;npole<3;npole++){
　　　　x=WINDOW_XSIZE/4*(npole+1);

　　　　dc.Rectangle(
　　　　　　　x-POLE_RADIUS　,TOP_MARGIN,
　　　　　　　x+POLE_RADIUS+1,WINDOW_YSIZE-BOTTOM_MARGIN+1);
　　　}

　　　UnsetPen　(&dc,&pen　,old_pen　);
　　　UnsetBrush(&dc,&brush,old_brush);
　　　　　　　　　　　　　　　　　　　　　　　　　　　//Write ring.
　　　old_pen　=SetPen　(&dc,&pen　,RING_COLOR);
　　　old_brush=SetBrush(&dc,&brush,RING_COLOR);

　　　for(npole=0;npole<3;npole++){
　　　　x=WINDOW_XSIZE/4*(npole+1);

　　　　y=WINDOW_YSIZE-BOTTOM_MARGIN;
　　　　for(nring=1;nring<MAX_RING;nring++){
　　　　　if(pole[npole][nring]){
　　　　　　xsize=POLE_RADIUS+RING_DELTA_RADIUS*pole[npole][nring];

　　　　　　dc.Rectangle(
　　　　　　　　　x-xsize　,y-RING_THICK,
　　　　　　　　　x+xsize+1,y+1　　　　 );
　　　　　}

　　　　　y-=(RING_THICK+RING_GAP);
　　　　}
　　　}

　　　UnsetPen　(&dc,&pen　,old_pen　);
　　　UnsetBrush(&dc,&brush,old_brush);

　　　return;
　　}
　/*
　* " Write one "
　*/
　　　　　　　　　　　　　　　　　　　　　　　　　　　//Write ring.
　　　　 if(write_mode==WRITE_MODE_NORMAL)color=RING_COLOR;
　　else if(write_mode==WRITE_MODE_FROM　)color=RING_FROM_COLOR;
　　else if(write_mode==WRITE_MODE_TO　　)color=RING_TO_COLOR;
　　else　　　　　　　　　　　　　　　　　color=BACK_COLOR;

　　old_pen　=SetPen　(&dc,&pen　,color);
　　old_brush=SetBrush(&dc,&brush,color);

　　x=WINDOW_XSIZE/4*(wpole+1);

　　y=WINDOW_YSIZE-BOTTOM_MARGIN;
　　y-=(wring-1)*(RING_THICK+RING_GAP);

　　xsize=POLE_RADIUS+RING_DELTA_RADIUS*pole[wpole][wring];

　　dc.Rectangle(
　　　　　x-xsize　,y-RING_THICK,
　　　　　x+xsize+1,y+1　　　　 );

　　UnsetPen　(&dc,&pen　,old_pen　);
　　UnsetBrush(&dc,&brush,old_brush);

　　if(write_mode==WRITE_MODE_ERASE){
　　　old_pen　=SetPen　(&dc,&pen　,POLE_COLOR);
　　　old_brush=SetBrush(&dc,&brush,POLE_COLOR);

　　　dc.Rectangle(
　　　　　　x-POLE_RADIUS　,y-RING_THICK,
　　　　　　x+POLE_RADIUS+1,y+1　　　　 );

　　　UnsetPen　(&dc,&pen　,old_pen　);
　　　UnsetBrush(&dc,&brush,old_brush);
　　}
　}

　/*======================== Message map of Hanoi class =======================
　* Message map of Hanoi class.
　*/
　BEGIN_MESSAGE_MAP(Hanoi,CFrameWnd)
　　ON_COMMAND(ID_IDLE,OnIdle)
　　ON_WM_PAINT()
　END_MESSAGE_MAP()

それではまた次回。