順列で魔方陣の解を検索する

全ての順列組み合わせを検索して、魔方陣になる並びを調べます。
3方陣では9の階乗、4方陣では16の階乗の組み合わせがあり、いかにパソコンが速いとは言え、4方陣が限度でした。

前田稔(Maeda Minoru)の超初心者のプログラム入門

プログラムの作成

  1. tbl[36] が順列組み合わせで魔方陣を検索する領域です。
    NUM が魔方陣のサイズで、3は3*3の魔方陣です。
    SUM は魔方陣の行(列)の合計で、メニューから設定した NUM を元に計算されます。
    ans[] は見つかった魔方陣を構成する組み合わせを記録する領域で、flag がその個数です。
    pos は現在表示中の ans[] の番号です。
    str[] はメッセージを表示する編集領域です。
        /***************************************************/
        /*★ 順列組み合わせで魔方陣を表示する    前田 稔 ★*/
        /***************************************************/
        #define     NAME    "魔方陣"
        #include    <windows.h>
        #include    "resource.h"
    
        HINSTANCE   g_hInst;
        HWND        g_hWnd;
        int         NUM= 3;
        int         SUM= 15;
        int         tbl[36];
        int         ans[36*10];
        int         flag= 0;
        int         pos= 0;
        char        str[160];
        
  2. WM_CREATE: では、NUM に 3 を設定して3魔方陣の検索を始めます。
            case WM_CREATE:
                NUM= 3;
                Search(hWnd);
                break;
        
  3. WM_PAINT: では、現在作成されている NUM の魔方陣を表示します。
            case WM_PAINT:
                hdc= BeginPaint (hWnd, &ps);
                Disp(hdc,NUM);
                EndPaint(hWnd, &ps);
                break;
        
  4. WM_COMMAND: でメニューから選択された魔方陣の検索を始めます。
    メニューから3方陣と4方陣が選べるようになっています。
    理論的には、魔方陣のサイズは自由ですが、時間的に4方陣が限度でしょう。
    4方陣でも検索に2分近くかかることを覚悟して下さい。
            case WM_COMMAND:
                switch(LOWORD(wParam))
                {   case IDM_3:  NUM= 3;    break;
                    case IDM_4:  NUM= 4;    break;
                    case IDM_EXIT:
                        SendMessage(hWnd,WM_CLOSE,0,0L);
                        return 0L;
                }
                Search(hWnd);
                InvalidateRect(hWnd,NULL,TRUE);
                break;
        
  5. 魔方陣は最大10個まで検索され、マウスの右クリックで次の表示に切り替えます。
    3方陣では、左右(上下)対象や回転も含め、80近くの魔方陣が検索されました。
            case WM_LBUTTONDOWN:
                pos= (pos+1)%flag;
                if (pos==0) MessageBox(NULL,"先頭の魔方陣です","Message Box",MB_OK);
                InvalidateRect(hWnd,NULL,TRUE);
                break;
        
  6. 魔方陣の検索を始める Search() 関数です。
    3方陣を超えると時間がかかるので、開始時刻を設定してマウスカーソルを砂時計に設定しています。
        // 魔方陣の検索
        void  Search(HWND hWnd)
        {   int     i,mx;
            SYSTEMTIME  STime;
            char        buf[32];
    
            GetLocalTime(&STime);
            wsprintf(buf,"開始時刻 %2d時 %2d分 %2d秒\n",STime.wHour,STime.wMinute,STime.wSecond);
            strcpy(str,buf);
            SetCapture(hWnd);
            SetCursor(LoadCursor(NULL,IDC_WAIT));
            flag= 0;
            mx= NUM*NUM;
            for(i=0; i<mx; i++) tbl[i]= i+1;
            SUM= (mx+1)*NUM/2;
            jyun(tbl,mx);
            ReleaseCapture();
            SetCursor(LoadCursor(NULL,IDC_ARROW));
            GetLocalTime(&STime);
            wsprintf(buf,"終了時刻 %2d時 %2d分 %2d秒",STime.wHour,STime.wMinute,STime.wSecond);
            strcat(str,buf);
            MessageBox(NULL,str,"Debug Message Box",MB_OK);
            pos= 0;
        }
        
  7. jyun() 関数は、魔方陣を構成する1~Nの数字を tbl[] に格納しておいて、全ての順列を設定する関数です。
    この関数から Check() 関数を呼び出して、魔方陣の組み合わせを判定します。
    詳細は 順列組み合わせを表示 を参照して下さい。
        // 順列を求める
        void  jyun(int t[], int n)
        {
        }
        
  8. 魔方陣の組み合わせを判定する関数です。
    tbl[] を二次元の配列に見立てて、行と列の合計をチェックします。
    魔方陣は10個まで検索されて ans[] に格納されます。
        // 魔方陣を判定する
        void  Check(int n)
        {   int     x,y,w;
    
            if (flag>9)     return;     //ans[] に魔方陣が格納されている
            for(y=0; y<n; y++)
            {   for(w=x=0; x<n; x++)  w+= tbl[y*n+x];
                if (w!=SUM) return;
                for(w=x=0; x<n; x++)  w+= tbl[x*n+y];
                if (w!=SUM) return;
            }
            for(x=0; x<n*n; x++)    ans[flag*NUM*NUM+x]= tbl[x];
            flag++;
        }
        
  9. 魔方陣を表示する Disp() 関数は前回と同じです。

【演習】

  1. jyun() 関数,Disp() を組み込んでプログラムを完成させて下さい。
  2. 現在のプログラムでは、全ての組み合わせを判定するために、非常に時間がかかります。
    順列の構成によっては、判定する必要の無い組み合わせも多く、これをパスできれば検索速度がアップします。
    プログラムを改良して、6方陣を表示して下さい。 (^_^;
    ちなみに6方陣の行(列)の合計は111になります。

超初心者のプログラム入門(Win32API C++)