/*
2000/07 ラドクリフの六角陣
coded by Isaku WADA
 ┌──────────────────────────────┐
 │ Fig. 2の19個の正六角形の中に,1から19までの19個の数すべて │
 │をダブりなく入れる。このとき,直線上に並んだ数(図中のA〜O)の│
 │和がどこも38になるようにしたい。何通りの配置が考えられるだろ│
 │うか。全体を回転した解や,裏返した解は別の解とはしない。  │
 │                              │
 │        O                     │
 │       N \                    │
 │      M \ \                   │
 │    L  \ \ \                  │
 │  K  \  ● ● ●───A             │
 │   \  \                       │
 │    \  ● ● ● ●──B             │
 │     \                        │
 │      ● ● ● ● ●─C             │
 │      /                        │
 │     /  ● ● ● ●──D             │
 │     /  /                       │
 │    J  /  ● ● ●───E             │
 │     I  /  /  /                  │
 │       H  /  /                   │
 │        G  /                   │
 │          F                    │
 │  Fig.2 ラドクリフの六角陣                │
 │                              │
 └──────────────────────────────┘
 ┌────────────────────────────┐
 │・プログラムの説明                   │
 │                            │
 │左上の六角形から以下のように a から s のローカル変数を割│
 │り当てます。                      │
 │                            │
 │  a b c                        │
 │ d e f g                        │
 │ h i j k l                       │
 │ m n o p                        │
 │  q r s                        │
 │                            │
 │プログラムは隅にある a,c,h,l,s,q と e の7つの変数で7重│
 │ループを構成して調べます。7つの変数の値が決まることで、│
 │残りの12個の変数は、制約条件より自動的に決まります。 │
 │                            │
 │隅にある6つの六角形のうち最小なものを、変数 a に固定す │
 │ることで、回転した解を取り除きます。さらに、c < h となる│
 │場合だけを調べて、裏返した解を取り除きます。      │
 │                            │
 │従って a は、範囲 1 から 14(19-5) までループし、c は a+1│
 │から 18 までループし、hは c+1 から 19 までループします。│
 │l,s,q は a+1 から 19 までループし、e は 1 から 19 までル│
 │ープします。                      │
 │                            │
 │配列 ok[-128〜127]は添え字が 1 以上 19 以下でまだ外側の │
 │ループ変数で使われていないときに 1 になります。添え字が │
 │0 以下、または、20 以上、または、外側のループ変数で使わ │
 │れているときは 0 になります。              │
 └────────────────────────────┘
 ┌────────────────────────────┐
 │・感想                         │
 │                            │
 │回転と裏返しを排除する方法を考えつくのに時間がかかりまし│
 │たが、それさえ分かれば、あとは、参考文献のおかげて、すん│
 │なりと解けました。プログラムもいつもより短く、サブルーチ│
 │ンも必要ありませんでした。               │
 └────────────────────────────┘
*/

#include <stdio.h>
#include <time.h>

/*
 * clock()
 *
 * clock() をサポートしない MS-DOS コンパイラ用の自前の clock()
 * LSI C-86 試食版でも 1/1000 秒単位の経過時間を返すようになる
 * Visual C++、Borland C++ Builder、UNIX などでは自動的に無視される
 *
 * 最初に clock() を呼び出すと必ず0を返す。
 * 2回目以降は、最初の呼び出しからの経過時間を 1/1000 秒単位で返す
 * 経過時間が24日以上になると−1を返す
 * 閏年も考慮に入れている
 */
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif

#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void)
{
    static int day[12]={0,31,59,90,120,151,181,212,243,273,304,334};
    union REGS t,d; static long Date0=0,Time0=0; long Time1,Date1;

    t.h.ah=0x2c; d.h.ah=0x2a;
    intdos(&t,&t); intdos(&d,&d);
    Time1=t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
    Date1=d.x.cx*365L+d.x.cx/4+day[d.h.dh-1]+d.h.dl;
    if ((d.x.cx%4)==0&&d.h.dh<=2) Date1--;
    if (Date0==0)  { Date0=Date1; Time0=Time1; return 0; }
    if (Date1-Date0>=24) return-1;
    return(Date1-Date0)*86400000L+Time1-Time0;
}
#endif

/*┌───────┐
 │メインルーチン│
 └───────┘*/
void main(void)
{
    double start=clock();
    static char tbl[256]; char*ok=tbl+128;
    int x,count=0,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s;

    for (x=1;x<=19;x++) ok[x]=1;
    for (a=1;a<=14;a++)                          { ok[a]=0;
    for (c=a+1;c<=18;c++)                        { ok[c]=0;
    b=38-a-c; if (!ok[b]) { ok[c]=1; continue; }   ok[b]=0;
    for (h=c+1;h<=19;h++) { if (!ok[h]) continue;  ok[h]=0;
    d=38-a-h; if (!ok[d]) { ok[h]=1; continue; }   ok[d]=0;
    for (l=a+1;l<=19;l++) { if (!ok[l]) continue;  ok[l]=0;
    g=38-c-l; if (!ok[g]) { ok[l]=1; continue; }   ok[g]=0;
    for (s=a+1;s<=19;s++) { if (!ok[s]) continue;  ok[s]=0;
    p=38-l-s; if (!ok[p]) { ok[s]=1; continue; }   ok[p]=0;
    for (q=a+1;q<=19;q++) { if (!ok[q]) continue;  ok[q]=0;
    r=38-q-s; if (!ok[r]) { ok[q]=1; continue; }   ok[r]=0;
    m=38-h-q; if (!ok[m]) { ok[r]=ok[q]=1; continue; }  ok[m]=0;
    for (e=1;e<=19;e++)   { if (!ok[e]) continue;
    ok[e]=0; f=38-d-e-g;
    if (!ok[f]) { ok[e]=1; continue; }
    ok[f]=0; i=38-b-e-m;
    if (!ok[i]) { ok[e]=ok[f]=1; continue; }
    ok[i]=0; k=38-b-f-p;
    if (!ok[k]) { ok[e]=ok[f]=ok[i]=1; continue; }
    ok[k]=0; n=38-d-i-r;
    if (!ok[n]) { ok[e]=ok[f]=ok[i]=ok[k]=1; continue; }
    ok[n]=0; o=38-g-k-r;
    if (!ok[o]) { ok[e]=ok[f]=ok[i]=ok[k]=ok[n]=1; continue; }
    ok[o]=0; j=38-c-f-n-q;
    if (!ok[j]) { ok[e]=ok[f]=ok[i]=ok[k]=ok[n]=ok[o]=1; continue; }
    if (a+e+j+o+s==38&&i+j+h+k+l==38&&m+n+o+p==38) {
        printf("解%d\n",++count);
        printf("    %4d%4d%4d\n",     a,b,c  );
        printf("  %4d%4d%4d%4d\n",   d,e,f,g );
        printf("%4d%4d%4d%4d%4d\n", h,i,j,k,l);
        printf("  %4d%4d%4d%4d\n",   m,n,o,p );
        printf("    %4d%4d%4d\n\n",   q,r,s  );
    }ok[o]=1;  ok[n]=1;  ok[k]=1;  ok[i]=1;  ok[f]=1; ok[e]=1;
    }ok[m]=1;  ok[r]=1;  ok[q]=1; }ok[p]=1;  ok[s]=1; }ok[g]=1;
     ok[l]=1; }ok[d]=1;  ok[h]=1; }ok[b]=1;  ok[c]=1; }ok[a]=1; }
    fprintf(stderr,"実行時間 %f\n",(clock()-start)/CLOCKS_PER_SEC);
}