/*
2001/01 等しく分かれた立方体
coded by Isaku WADA
 ┌──────────────────────────────┐
 │ Fig. 2のような3×3×3の立方体がある.これを構成している27 │
 │個の単位立方体には,Fig. 3のように1〜27の番号がふってある。 │
 │ この立方体を2つの塊に切り分け,それぞれに属する番号を足し│
 │あわせたところ,同じになったという。このような切り分け方は何│
 │通りあるだろうか。                     │
 │ ただし,切り分けた2つの塊が,平行移動で分離することができ│
 │る場合に限る。たとえば2つの塊がFig. 4のようになった場合は, │
 │平行移動でははずせないので解とはしない。また,「塊」は,単位│
 │立方体どうしが面でくっついてできており,辺や頂点だけで接触し│
 │ている単位立方体はつながっていることにならない。      │
 └──────────────────────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │ 立方体をXYZ方向のいずれかの平行移動で分離することができ│
 │たとします。まず、分離できた方向から見て、手前の塊をA、奥の│
 │塊をBとします。ここで、分離できた方向から光を当て、影となる│
 │3×3平面の各々の影について着目します。さらに、ひとつの影の│
 │元になった立方体のうちのAの個数を配列int Status[9]で表すこ │
 │とにします。すると、ある方向で分離できる全ての切り分け方は、│
 │この配列で一意に表すことができます。例えば、Status[9]が   │
 │{1,1,1,1,1,1,1,1,1}の場合は、手前の9個がAで、残りの18個 │
 │がBとなります。                      │
 │                              │
 │ プログラムは、配列Status[9]のとり得る全ての組み合わせを生 │
 │成します。組み合わせは{0,0,0,0,0,0,0,0,0}から        │
 │{3,3,3,3,3,3,3,3,3}まで、4の9乗通り(=262144)あります。そし│
 │て、XYZの3方向各々について、用意しておいた足し算表を使っ│
 │て塊Aの番号を足し合わせます。ここで、合計が189ならば、飛び │
 │地がないことを確認して、カウントしてゆきます。このとき、1方│
 │向しか平行移動できない場合は、Count1を増やし、2方向同時に平│
 │行移動できる場合は、Count2 を増やし、3方向同時に平行移動可 │
 │能な場合は、Count3 を増やします。数え終わったら、      │
 │Count1+Count2/2+Count3/3をパズルの解答として出力します。  │
 │                              │
 │ 細かな工夫として第1に、番号の足し算は、毎回全部の塊Aの番│
 │号を足すのではなく、変化があった部分だけを足したり引いたりし│
 │ました。第2に、飛び地の判定や平行移動の判定に、ビット演算を│
 │用いました。                        │
 └──────────────────────────────┘
 ┌──────────────────────────────┐
 │・感想                           │
 │                              │
 │ 今回のパズルは、解が千通り以上もあるので、全部の結果を見て│
 │確かめることができませんでした。この解が正しいかどうか、あま│
 │り自信がありません。                    │
 └──────────────────────────────┘
 Visual C++, Borland C++, LSI C-86, Turbo C で動作確認
 ただし、N=4 の場合、LSI C, Turbo C ではコンパイルできない
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 3 /* 1辺の長さ。2 か 3 か 4 */
#define P 0 /* 解を表示しないなら 0 */

/*┌────────────────────┐
 │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

#if N == 4
#ifdef UNIX
#define LONG long long
#else
#define LONG __int64
#endif
#else
#define LONG long
#endif

/*┌──────────────────────┐
 │足し算表:3次元のそれぞれの軸について求める │
 └──────────────────────┘*/
int NumX[N][N*N];  /* 例えば N=2 なら {1,2,3,4},{5,6,7,8} */
int NumY[N][N*N];  /* 例えば N=2 なら {1,5,2,6},{3,7,4,8} */
int NumZ[N][N*N];  /* 例えば N=2 なら {1,3,5,7},{2,4,6,8} */
int SumX[N*N],SumY[N*N],SumZ[N*N]; /* NumX,NumY,NumZ の総和 */

/*┌─────────────────────────────┐
 │特定の方向から見た場合の、境目の奥行きの位置を指定する    │
 │例えば N=2 なら {0,0,0,0} から {2,2,2,2} までの状態をとる │
 └─────────────────────────────┘*/
char Status[N*N];

/*┌────────────────────────┐
 │各方向から見た場合のN層マスク(重解の判定に使う)│
 └────────────────────────┘*/
int MaskX[N],MaskY[N],MaskZ[N];

LONG XorBits,XorMask; /* 他方の集合を得る時に XOR で使う */
LONG AdjMat[N*N*N];   /* 隣接行列。1要素1ビットなので1次元配列 */
int  HalfSum;         /* 総和の半分の値 */
int  Count1,Count2,Count3; /* 単独解の数、2重解の数、3重解の数 */

#if P != 0
/*┌──────┐
 │解を表示する│
 └──────┘*/
void Print(LONG bits)
{
    int i,j,k,u; static int PrintCount;

    printf("%d:\n",++PrintCount);
    for (i=0;i<N;i++) {
        for (j=0;j<N;j++) {
            for (k=0;k<N;k++) {
                u=i*N+j*N*N+k;
                printf(((LONG)1<<u)&bits?"%3d":"  .",u+1);
            }
            if (j<N-1) printf("  ");
        }
        printf("  --  ");
        for (j=0;j<N;j++) {
            for (k=0;k<N;k++) {
                u=i*N+j*N*N+k;
                printf(((LONG)1<<u)&bits?"  .":"%3d",u+1);
            }
            if (j<N-1) printf("  ");
        }
        printf("\n");
    }
    printf("\n");
}

/*┌───────────────────────────┐
 │必要に応じて解を表示する(一度表示したものは表示しない)│
 └───────────────────────────┘*/
void PrintIfNeed(int NumOfDir,LONG bits)
{
    static int Count23; static LONG Table[N==4?65536L:512]; int i;

    if (NumOfDir==1) { Print(bits); return; }
    for (i=0;i<Count23;i++) if (Table[i]==bits) break;
    if (i<Count23) return;
    Print(bits);
    if (Count23==sizeof Table/sizeof*Table)
    { fprintf(stderr,"Table[]が小さすぎます\n"); exit(1); }
    Table[Count23++]=bits;
}
#endif

/*┌──────────────────────────┐
 │飛び地があれば1. 塊ならば0. 隣接行列を利用している│
 └──────────────────────────┘*/
int Enclave(LONG bits)
{
    int s; LONG curr,prev;

    for (curr=1;(bits&curr)==0;curr<<=1) ; /* 出発点を決める */
    do {
        prev=curr;
        /* 新たに移動できるビットを立てる */
        for (s=0;s<N*N*N;s++) if (((LONG)1<<s)&curr)
            curr|=AdjMat[s]&bits;
    } while (curr!=prev); /* 変化しなくなるまで続ける */
    return curr!=bits; /* 元の状態にならなければ飛び地がある */
}

/*┌─────────────────────────────┐
 │指定された方向へ平行移動できれば1を返す(重解の判定に使う)│
 └─────────────────────────────┘*/
int Movable(int mask[])
{
    int i;

    for (i=1;i<N;i++) if (~mask[i-1]&mask[i]) break;
    if (i==N) return 1;
    for (i=1;i<N;i++) if (mask[i-1]&~mask[i]) break;
    if (i==N) return 1;
    return 0;
}

/*┌───────────────────────────┐
 │現在の Status と与えられた方向で条件を満たせば解とする│
 └───────────────────────────┘*/
void Test(int num[][N*N])
{
    int i,j,k,NumOfDir=1,t=0; LONG bits=0;

    for (i=0;i<N*N;i++) for (j=0;j<Status[i];j++)
        bits|=(LONG)1<<(num[j][i]-1); /* ビットパターンを求める */
    if (Enclave(bits)||Enclave(bits^XorBits)) return; /* 飛び地 */
    /* 自明の1方向を除く2方向について、N層マスクを求める */
    for (i=0;i<N;i++) MaskX[i]=MaskY[i]=MaskZ[i]=0;
    for (i=0;i<N;i++) for (j=0;j<N;j++) for (k=0;k<N;k++,t++)
     if (((LONG)1<<t)&bits) {
         if (num!=NumX) MaskX[i]|=1<<(j*N+k);
         if (num!=NumY) MaskY[j]|=1<<(k*N+i);
         if (num!=NumZ) MaskZ[k]|=1<<(i*N+j);
     }
    /* 平行移動できる方向数が NumOfDir に求まる */
    if (num!=NumX&&Movable(MaskX)) NumOfDir++;
    if (num!=NumY&&Movable(MaskY)) NumOfDir++;
    if (num!=NumZ&&Movable(MaskZ)) NumOfDir++;
    if (NumOfDir==1) Count1++;
    else if (NumOfDir==2) Count2++; else Count3++;
    /* 途中経過の表示 */
    if ((Count1&65535L)==0&&Count1) {
        fprintf(stderr,"%9d  ",Count1+Count2/2+Count3/3);
        for (i=N*N-1;i>=0;i--) fprintf(stderr,"%d",Status[i]);
        fprintf(stderr,"\n");
    }
#if P != 0
    PrintIfNeed(NumOfDir,bits);
#endif
}

/*┌───┐
 │初期化│
 └───┘*/
void Initialize(void)
{
    int i,j,k,u; LONG adj;

    u=HalfSum=Count1=Count2=Count3=0;
    for (i=0;i<N*N;i++) SumX[i]=SumY[i]=SumZ[i]=Status[i]=0;
    for (i=0;i<N;i++) for (j=0;j<N;j++) for (k=0;k<N;k++) {
        /* 隣接行列を求める */
        adj=0;
        if (i>0)   adj|=(LONG)1<<(u-N*N);
        if (i<N-1) adj|=(LONG)1<<(u+N*N);
        if (j>0)   adj|=(LONG)1<<(u-N);
        if (j<N-1) adj|=(LONG)1<<(u+N);
        if (k>0)   adj|=(LONG)1<<(u-1);
        if (k<N-1) adj|=(LONG)1<<(u+1);
        AdjMat[u]=adj;
        /* XorBits と HalfSum を計算する */
        XorBits|=(LONG)1<<u; u++; HalfSum+=u;
        /* 足し算表を作る */
        NumX[i][j*N+k]=u; SumX[j*N+k]+=u;
        NumY[j][k*N+i]=u; SumY[k*N+i]+=u;
        NumZ[k][i*N+j]=u; SumZ[i*N+j]+=u;
    }
    for (i=u=0;i<N;i++) for (j=0;j<N;j++,u++) XorMask|=(LONG)1<<u;
    HalfSum/=2;
}

/*┌──────┐
 │メインループ│
 └──────┘*/
void MainLoop(void)
{
    int i,j,k,CurX=0,CurY=0,CurZ=0;

    for (;;) {
        if (CurX==HalfSum) Test(NumX);
        if (CurY==HalfSum) Test(NumY);
        if (CurZ==HalfSum) Test(NumZ);
        /* 次の Status と CurX と CurY と CurZ を求める */
        for (i=0;i<N*N;i++) if (Status[i]!=N) break;
        if (i==N*N) break;
        k=Status[i]++;
        CurX+=NumX[k][i]; CurY+=NumY[k][i]; CurZ+=NumZ[k][i];
        for (j=0;j<i;j++) {
            Status[j]=0;
            CurX-=SumX[j]; CurY-=SumY[j]; CurZ-=SumZ[j];
        }
    }
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
void main(void)
{
    int t; double StartTime=clock();

    for (t=0;t<1;t++) { Initialize(); MainLoop(); }
    printf("解の総数=%d  ",Count1+Count2/2+Count3/3);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
}