/*
2001/04 隣差方陣
coded by Isaku WADA
 ┌──────────────────────────────┐
 │Fig. 4のように,3×3のマスの中に9個の数を書き込んでみた。こ │
 │こで,隣り合った2数(ナナメは考えない)の差の絶対値を「隣差」と │
 │呼ぶことにする。すると,Fig. 4にある12か所の隣差において, │
 │1〜12すべての数が登場している。このように,隣差が1〜12にな │
 │る,9個の数の配置は何通りあるか。なお,書き込む9個の数は1以 │
 │上の相異なる整数とし,回転・鏡像の解を除く。また,ある解が │
 │あったときに,それを構成する9個の数全体に同じ数を足したもの │
 │も解となってしまうので,必ず“1”は使うものとする。     │
 │                              │
 │ Fig.4 隣差方陣の例                     │
 │┌─┬─┬─┐                       │
 ││6│1│13│                       │
 │├─┼─┼─┤                       │
 ││14│10│20│                       │
 │├─┼─┼─┤                       │
 ││8│7│18│                       │
 │└─┴─┴─┘                       │
 └──────────────────────────────┘

 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │  ┌───┬───┬───┐               │
 │  │   │   │   │               │
 │  │ a j b k c │               │
 │  │   │   │   │               │
 │  ├─l─┼─m─┼─n─┤               │
 │  │   │   │   │               │
 │  │ d o e p f │               │
 │  │   │   │   │               │
 │  ├─q─┼─r─┼─s─┤               │
 │  │   │   │   │               │
 │  │ g t h u i │               │
 │  │   │   │   │               │
 │  └───┴───┴───┘               │
 │   図1                          │
 │                              │
 │9個の数と12個の隣差を表す変数に、図1のような名前を付けます。│
 │ただし、隣差には絶対値ではなく、単に右か下の数から左か上の数│
 │を引いた値を記録します。                  │
 │                              │
 │ここで、(1)「aが1」、(2)「bが1」、(3)「eが1」の3通りの場合 │
 │分けをします。(1)と(2)の場合は、順に隣差j,l,m,k,n,q,r,sにつ │
 │いて-12〜12のループを作ります。(3)の場合は、隣差m,j,o,k,n, │
 │q,r,sについてループを作ります。残りの数と隣差はループの隣差 │
 │が決まるにつれ自動的に決まります。例えば(1)の場合、jを決めれ│
 │ばbが決まり、lを決めればdが決まり、mを決めればeとoが決まりま│
 │す。                            │
 │                              │
 │プログラム中(1),(2),(3)のn,q,r,sループは全く同じなので、関数│
 │を使って共有しました。                   │
 │                              │
 │また、9個の数が互いに異なるように、フラグの配列NumFlg[39]を │
 │用意します。さらに、12個の隣差が互いに異なるように、    │
 │NeiFlg[13]も用意します。変数が新しく決まる毎にこれらを参照し│
 │て、同じ数や隣差が現れないようにします。          │
 │                              │
 │回転と鏡像を排除するために、(1)の場合はb<d、(2)の場合はa<c、│
 │(3)の場合はb==2かつa<c、あるいは|j|==1とします。      │
 └──────────────────────────────┘
 ┌──────────────────────────────┐
 │・感想                           │
 │                              │
 │4×4にも挑戦しましたが、計算に何日もかかりそうなのであきらめ│
 │ました。代わりに、4×3を解いたところ2時間12分18秒で2億6734万│
 │1320という結果を得ました。                 │
 └──────────────────────────────┘
 Visual C++, Borland C++, LSI C-86, Turbo C で動作確認
*/
#include <stdio.h>
#include <time.h>

/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#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) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

/* 9個の数と12個の隣差を表す変数
 ┌───┬───┬───┐
 │   │   │   │
 │ a j b k c │
 │   │   │   │
 ├─l─┼─m─┼─n─┤
 │   │   │   │
 │ d o e p f │
 │   │   │   │
 ├─q─┼─r─┼─s─┤
 │   │   │   │
 │ g t h u i │
 │   │   │   │
 └───┴───┴───┘
*/

/*┌─────┐
 │変数の宣言│
 └─────┘*/
int a,b,c,d,e,f,g,h,i;
int j,k,l,m,n,o,p,q,r,s,t,u;
int AbsA;            /* 自明な隣差の絶対値                  */
char NeiFlg[13]={1}; /* 隣差を既に使用していれば 1          */
char NumFlg[39];     /* 書き込む数字を既に使用していれば 1  */
long Count;          /* 得られた配置の数                    */
double StartTime;    /* プログラムを開始した時の clock() 値 */

/*┌───┐
 │絶対値│
 └───┘*/
#define ABS(A) ((A)>0?(A):-(A))

/*┌─────────────────────────┐
 │ループを作成するマクロ                            │
 │F が 0 なら順方向に隣差を決める。F が 1 なら逆方向│
 │A : ループを制御する隣差                          │
 │X : 新しく決定される数字                          │
 │Y : X を決めるのに必要な数字                      │
 └─────────────────────────┘*/
#define LOOP(F,A,X,Y) \
    for (A=-12;A<=12;A++) {           /* ループ本体           */ \
        if (NeiFlg[ABS(A)]) continue; /* 隣差が使われている   */ \
        X=Y+(F?-A:A);                 /* 隣差から数字を求める */ \
        if (X<=1) continue;           /* 数字が負             */ \
        if (NumFlg[X]) continue;      /* 数字が使われている   */ \
        NumFlg[X]=NeiFlg[ABS(A)]=1;   /* フラグを立てる       */

/*┌───────────────────────┐
 │自明な隣差を設定し、条件を満たせば続けるマクロ│
 └───────────────────────┘*/
#define TRIV(A,X,Y,Z) \
    A=X+Y-Z; /* 自明な隣差を求める */ \
    AbsA=ABS(A); \
    if (AbsA<=12&&NeiFlg[AbsA]==0) { \
        NeiFlg[AbsA]=1;

/*┌─────────────────┐
 │フラグを戻し、ループを閉じるマクロ│
 └─────────────────┘*/
#define EOL(A,X) NeiFlg[ABS(A)]=NumFlg[X]=0; }

/*┌──────────┐
 │if 文を閉じるマクロ │
 └──────────┘*/
#define EOT(A) NeiFlg[ABS(A)]=0; }

/*┌───────┐
 │配置を表示する│
 └───────┘*/
void Print(void)
{
    printf("\x1b[%s\n %ld\n\n",Count==1?"2J":"1;1H",Count);
    printf("%3d%3d%3d |%5d%4d\n",   a,b,c,  j,k );
    printf("          |%3d%4d%4d\n",       l,m,n);
    printf("%3d%3d%3d |%5d%4d\n",   d,e,f,  o,p );
    printf("          |%3d%4d%4d\n",       q,r,s);
    printf("%3d%3d%3d |%5d%4d\n",   g,h,i,  t,u );
    /*{ char bf[99]; printf("\n > "); fgets(bf,sizeof bf,stdin); }*/
}

/*┌─────┐
 │共通ループ│
 └─────┘*/
void CommonLoops(void)
{
    LOOP(0,n,f,c) TRIV(p,k,n,m) LOOP(0,q,g,d) LOOP(0,r,h,e)
    TRIV(t,o,r,q) LOOP(0,s,i,f) TRIV(u,p,s,r) Count++;/*Print();*/
    EOT(u) EOL(s,i) EOT(t) EOL(r,h) EOL(q,g) EOT(p) EOL(n,f)
}

/*┌────────────────┐
 │a が1で題意を満たす配置を求める│
 └────────────────┘*/
void sub1(void)
{
    a=1; LOOP(0,j,b,a) LOOP(0,l,d,a)
    if (b<d) {
        LOOP(0,m,e,b) TRIV(o,j,m,l) LOOP(0,k,c,b)
        CommonLoops(); EOL(k,c) EOT(o) EOL(m,e)
    }
    EOL(l,d) EOL(j,b)
}

/*┌────────────────┐
 │b が1で題意を満たす配置を求める│
 └────────────────┘*/
void sub2(void)
{
    b=1; LOOP(1,j,a,b) LOOP(0,l,d,a) LOOP(0,m,e,b)
    TRIV(o,j,m,l) LOOP(0,k,c,b)
    if (a<c) CommonLoops();
    EOL(k,c) EOT(o) EOL(m,e) EOL(l,d) EOL(j,a)
}

/*┌────────────────┐
 │e が1で題意を満たす配置を求める│
 └────────────────┘*/
void sub3(void)
{
    e=1; LOOP(1,m,b,e) LOOP(1,j,a,b)
    if (b==2||j==1||j==-1) {
        LOOP(1,o,d,e) TRIV(l,j,m,o) LOOP(0,k,c,b)
        if (b!=2||a<c) CommonLoops();
        EOL(k,c) EOT(l) EOL(o,d)
    } 
    EOL(j,a) EOL(m,b)
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(void)
{
    StartTime=clock(); sub1(); sub2(); sub3(); printf("%ld ",Count);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}