/*
2003/09 カラーボールピラミッド
coded by Isaku WADA
 ┌──────────────────────────────┐
 │ Fig.3のように,2つの球をつないだ5ピース(A〜E)があり,│
 │各球には色が塗ってある。この5ピースを使って,Fig.4のような│
 │ピラミッド(正確には正四面体)状に組むのだが,「同じ色の球が接│
 │しないように」というのが条件だ。全体を回転したものや鏡像のも│
 │のは別の解とはしないで,何通りの組み方があるだろうか。   │
 │                              │
 │Fig.3 5ピースのカラーボール               │
 │A(緑)(赤) B(青)(赤) C(青)(黄) D(赤)(黄) E(緑)(黄) │
 │                              │
 │Fig.4 カラーボールを使ったピラミッド           │
 │ ○   ○   ○                    │
 │ ○○  ○○                        │
 │○○○                           │
 │                              │
 └──────────────────────────────┘
 ┌──────┐
 │解答:4通り│
 └──────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │ 実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.007093秒│ 36864 byte │
 │Microsoft Visual C++ .NET  │0.006734秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │0.010172秒│ 54784 byte │
 │gcc-2.953(djgpp)      │0.007912秒│ 109080 byte │
 │gcc-2.953(cygwin)      │0.007781秒│ 20303 byte │
 │LSI C-86 Ver 3.30 試食版  │0.019830秒│ 13916 byte │
 │Turbo C Ver 1.5(small model)│0.018240秒│ 11332 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP    │
 └──────────────┴─────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │Fig.1                          │
 │ 0  6  9                     │
 │ 12 78                        │
 │345                          │
 │                             │
 │ まず、Fig.1のようにピラミッドの各位置に番号をつけます。│
 │そして、行列AdjMat[10][10]を用意します。位置u,vが隣り合う │
 │ならば、AdjMat[u][v]は1になり、離れていれば0になるように│
 │しておきます。                      │
 │ プログラム実行中に、どのようにピラミッドが組まれたかは、│
 │Map[10]とColor[10]の2つの配列に記録します。Mapはどのピー │
 │スが置かれたかを記録し、Colorはどの色が置かれたかを記録し │
 │ます。                          │
 │ 探索は、再帰呼び出しの深さが、ピースの数と等しくなる関数│
 │で行います。関数はuとvを制御変数とした2重forループを持ち │
 │ます。ループの先頭でAdjMat[u][v]が0ならばスキップします。│
 │また、Color[u]やColor[v]に既に色が置かれていたらスキップし│
 │ます。さらにuやvに隣接するColorに現在のピースと同じ色が置 │
 │かれていてもスキップします。ここまで到達できたら現在のピー│
 │スをMapとColorに記録します。そして、ピースが残っていたら再│
 │帰呼び出しをして、次のピースを置きます。全てのピースを置く│
 │ことができたら、回転と鏡像を排除してカウントします。   │
 │ 回転と鏡像の排除は、頂点に置かれたピースの番号の大小関係│
 │で行います。まず、回転を排除するために、頂点0が他の3つの│
 │頂点よりも小さいものに制限します。さらに、残った3つの頂点│
 │のうちで、頂点3が最も小さい場合に制限します。これで回転は│
 │全て排除できます。そして、鏡像を排除するために、頂点5が頂│
 │点9よりも小さい場合に制限します。結果、頂点0<頂点3<頂│
 │点5<頂点9となれば、回転と鏡像は排除されます。     │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 回転と鏡像の排除をどのようにして行うかに、かなり悩みまし│
 │た。                           │
 └─────────────────────────────┘*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*┌─────┐
 │定数の宣言│
 └─────┘*/
enum { P=5, N=10 }; /* ピースの数とピラミッドの大きさ */
enum { NONE, GREEN, RED, BLUE, YELLOW }; /* 色の定義 */

/* ピラミッド表示用の文字列 */
char MapStr[][3]  ={"A","B","C","D","E"};
char ColorStr[][3]={"・","緑","赤","青","黄"};

/* ピースの色   A     B    C      D      E     */
int ColorU[P]={ GREEN, BLUE, BLUE,   RED,    GREEN  };
int ColorV[P]={ RED,   RED,  YELLOW, YELLOW, YELLOW };

/*  0  6  9 */
/*  12 78    */
/* 345      */
int AdjMat[N][N]= /* uとvが隣りならば AdjMat[u][v]==1 */
 { { 0,1,1,0,0,0, 1,0,0, 0 },
   { 1,0,1,1,1,0, 1,1,0, 0 },
   { 1,1,0,0,1,1, 1,0,1, 0 },
   { 0,1,0,0,1,0, 0,1,0, 0 },
   { 0,1,1,1,0,1, 0,1,1, 0 },
   { 0,0,1,0,1,0, 0,0,1, 0 },
   { 1,1,1,0,0,0, 0,1,1, 1 },
   { 0,1,0,1,1,0, 1,0,1, 1 },
   { 0,0,1,0,1,1, 1,1,0, 1 },
   { 0,0,0,0,0,0, 1,1,1, 0 } };

/*┌─────┐
 │変数の宣言│
 └─────┘*/
int Map[N];    /* ピースの置き方を記録 */
int Color[N];  /* 色の置き方を記録 */
int NumOfSol;  /* 解の数 */
int PrintFlag; /* 解を書き出すかどうかのフラグ */

/*┌─────────────┐
 │MapとColorの内容を書き出す│
 └─────────────┘*/
#define M(X) MapStr[Map[X]]
#define C(X) ColorStr[Color[X]]
void Print(void)
{
    printf("  %s    %s   %s   ",M(0),M(6),M(9));
    printf("  %s    %s   %s\n", C(0),C(6),C(9));
    printf(" %s%s  %s%s       ",M(1),M(2),M(7),M(8));
    printf(" %s%s  %s%s\n",     C(1),C(2),C(7),C(8));
    printf("%s%s%s            ",M(3),M(4),M(5));
    printf("%s%s%s\n\n",        C(3),C(4),C(5));
}

/*┌──────────────────┐
 │再帰呼び出しをしながら、パズルを解く│
 └──────────────────┘*/
void Solve(int piece)
{
    int i,u,v;

    /* 全ての場所の組み合わせで繰り返す */
    for (u=0;u<N;u++) for (v=0;v<N;v++) {

        /* 隣でない場合や既に置かれている場合はスキップする */
        if (AdjMat[u][v]==0||Color[u]||Color[v]) continue;

        /* 隣に同じ色が置かれていればスキップする */
        for (i=0;i<N;i++)
         if ((AdjMat[u][i]&&Color[i]==ColorU[piece])||
             (AdjMat[v][i]&&Color[i]==ColorV[piece])) break;
        if (i<N) continue;

        Map[u]=Map[v]=piece;
        Color[u]=ColorU[piece];
        Color[v]=ColorV[piece];

        if (piece==P-1) { /* 全て置けた */

            /* 回転と鏡像のチェック */
            if (Map[0]<Map[3]&&Map[3]<Map[5]&&Map[5]<Map[9]) {
                NumOfSol++;
                if (PrintFlag) Print();
            }

        } else
            /* 次のピースを置くために再帰呼び出しする */
            Solve(piece+1);

        Color[u]=Color[v]=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

/*┌────────┐
 │メイン・ルーチン│
 └────────┘*/
int main(int argc,char**argv)
{
    double StartTime=clock(); int i,num;

    if (argc==2) num=atoi(argv[1]); else num=1;
    for (i=0;i<num;i++) { PrintFlag=(i==0); NumOfSol=0; Solve(0); }
    printf("解の数 %d 個  ",NumOfSol);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return EXIT_SUCCESS;
}