/*
2002/11 8コイーンプロブレム
coded by Isaku WADA
 ┌───────────────────────────┐
 │ 10円玉5枚と100円玉3枚がある。これを5×5の盤│
 │の上にすべて置きたい。ただし,10円玉と100円玉が同│
 │じ縦,横,ななめ45度の線上にこないことが条件。同じコ│
 │インが同一線上にあるのはかまわない。各マスにコインは1│
 │枚しか入れない。Fig.2は,5枚配置したところで手詰まっ│
 │てしまった失敗例だ。全体を回転したり,鏡像となっている│
 │ものは別の解とはしないで,8枚のコインすべてを配置した│
 │パターンは何通りあるだろうか。            │
 │                           │
 │ Fig.2 失敗例                   │
 │                           │
 │ ┌─┬─┬─┬─┬─┐               │
 │ │ │百│ │ │ │十              │
 │ ├─┼─┼─┼─┼─┤               │
 │ │百│ │ │ │ │十              │
 │ ├─┼─┼─┼─┼─┤               │
 │ │ │ │十│ │十│十              │
 │ ├─┼─┼─┼─┼─┤               │
 │ │ │ │ │ │ │               │
 │ ├─┼─┼─┼─┼─┤               │
 │ │ │ │ │百│ │               │
 │ └─┴─┴─┴─┴─┘               │
 │                           │
 └───────────────────────────┘
 ┌───────────────────────────┐
 │解答:1通り                     │
 ├───────────────────────────┤
 │ ┌─┬─┬─┬─┬─┐               │
 │ │ │十│十│ │ │               │
 │ ├─┼─┼─┼─┼─┤               │
 │ │ │ │ │ │百│               │
 │ ├─┼─┼─┼─┼─┤               │
 │ │十│ │ │ │ │               │
 │ ├─┼─┼─┼─┼─┤               │
 │ │十│十│ │ │ │               │
 │ ├─┼─┼─┼─┼─┤               │
 │ │ │ │ │百│百│               │
 │ └─┴─┴─┴─┴─┘               │
 └───────────────────────────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.00295 秒│ 36864 byte │
 │Microsoft Visual C++ .NET  │0.00282 秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │0.00298 秒│ 54272 byte │
 │gcc-2.953(djgpp)      │0.00335 秒│ 109667 byte │
 │gcc-2.953(cygwin)      │0.00348 秒│ 21057 byte │
 │LSI C-86 Ver 3.30 試食版  │0.00599 秒│ 14098 byte │
 │Turbo C Ver 1.5(small model)│0.00571 秒│ 11428 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │   OS:Windows XP   │
 └──────────────┴─────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │異なるコインが線上にこないことを確かめるために、縦方向の直線│
 │を調べるのに5個、横に5個、右上がりの斜めに9個、右下がりの│
 │斜めに9個の、小計28個分のカウンタを、10円玉、100円玉│
 │の2種類について、合計56個用意します。カウンタはフラグのよ│
 │うに使います。                       │
 │                              │
 │コインを置く順番は、効率をよくするために、10円玉、100円│
 │玉、10円玉、100円玉、10円玉、100円玉、10円玉、1│
 │0円玉の順にします。                    │
 │                              │
 │10円玉を置くときは、縦横斜めの100円玉該当カウンタを見て│
 │全て0ならば置きます。そして、置くことができた場合は、縦横斜│
 │めの10円玉該当カウンタをインクリメントします。      │
 │                              │
 │逆に、100円玉を置くときは、縦横斜めの10円玉該当カウンタ│
 │を見て、全て0ならば置きます。そして、置くことができた場合は│
 │縦横斜めの100円玉該当カウンタをインクリメントします。  │
 │                              │
 │コインの位置として、10円玉、100円玉それぞれについて、左│
 │上からはじめ、右下へ向かって置いてゆきます。例えば、ある位置│
 │に10円玉を置いた場合、それ以降にその位置より左上に10円玉│
 │を置くことはありません。                  │
 │                              │
 │8枚のコインを全て置くことができたら、回転と鏡像を排除するた│
 │めに、右90度回転を3回、左右反転を1回、さらに、右90度回│
 │転を3回行いながら、過去の解と比較します。新しい解ならば記録│
 │して次に進みます。                     │
 ├──────────────────────────────┤
 │・感想                           │
 │                              │
 │コインの枚数を7枚に減らして結果を見ると、個性的な配置が多く│
 │あり、楽しめました。                    │
 └──────────────────────────────┘
*/

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

/*┌─────┐
 │定数の宣言│
 └─────┘*/
#define C 8  /* コインの数 */
#define N 5  /* 盤の大きさ */
#define L 34 /*Logの大きさ */
#define A 1  /*100円玉のID */
#define B 2  /* 10円玉のID */

/*┌─────┐
 │変数の宣言│
 └─────┘*/
char Order[]=
   {B,A,B,A,B,A,B,B}; /* コインを置く順番       */
char Tate[2][N];      /* 縦方向の占有カウンタ   */
char Yoko[2][N];      /* 横方向の占有カウンタ   */
char Slash[2][2*N-1]; /* 右上がりの占有カウンタ */
char BkSls[2][2*N-1]; /* 右下がりの占有カウンタ */
char Map[N][N];       /* 主に使用する盤         */
char Buf[N][N];       /* 回転・鏡像の盤         */
char Log[L][N][N];    /* ログ                   */
int  LogSize;         /* 解の数                 */

/*┌────┐
 │解の表示│
 └────┘*/
void Print(char map[N][N])
{
    int i,j; static int n;

    printf("%d:\n",++n);
    for (i=0;i<N;i++) {
        for (j=0;j<N;j++)
            printf("%.2s","・百十\n"+2*map[i][j]);
        printf("\n");
    }
    printf("\n");
}

/*┌───────┐
 │ログと比較する│
 └───────┘*/
int Compare(void)
{
    int i;

    for (i=0;i<LogSize;i++)
     if (memcmp(Buf,Log[i],N*N)==0) return 1;
    return 0;
}

/*┌─────────────────┐
 │盤 Buf を90度右回りに回転させる │
 └─────────────────┘*/
int Rotate(void)
{
    char tmp[N][N]; int i,j;

    memcpy(tmp,Buf,N*N);
    for (i=0;i<N;i++) for (j=0;j<N;j++)
        Buf[j][N-1-i]=tmp[i][j];
    return Compare();
}

/*┌────────────┐
 │盤 Buf を上下反転させる │
 └────────────┘*/
int TurnOver(void)
{
    char tmp[N][N]; int i,j;

    memcpy(tmp,Buf,N*N);
    for (i=0;i<N;i++) for (j=0;j<N;j++)
        Buf[N-1-i][j]=tmp[i][j];
    return Compare();
}

/*┌────────────────────────────┐
 │得られた Map を過去ログと比較して新しいものなら登録する │
 └────────────────────────────┘*/
void CheckLog(void)
{
    memcpy(Buf,Map,N*N);
    if (Compare() ||Rotate()||Rotate()||Rotate()) return;
    if (TurnOver()||Rotate()||Rotate()||Rotate()) return;
    if (LogSize==L) { printf("L is small\n"); exit(1); }
    memcpy(Log[LogSize++],Map,N*N);
}

/*┌────────────────────────────┐
 │解の探索(引数のtopA,topBはどこから探索を始めるかを示す) │
 └────────────────────────────┘*/
void Solve(int level,int topA,int topB)
{
    int i,j,t=0,x;

    if (level==C) { CheckLog(); return; }
    x=Order[level]-1; /* A:x=0   B:x=1 */
    for (i=0;i<N;i++) for (j=0;j<N;j++,t++)
     if ((x==0?t>=topA:t>=topB)&&Map[i][j]==0)
      if (Tate[1-x][j]==0&&Yoko[1-x][i]==0)
       if (Slash[1-x][i+j]==0&&BkSls[1-x][N-1+i-j]==0) {
           Map[i][j]=(char)(x+1); Tate[x][j]++; Yoko[x][i]++;
           Slash[x][i+j]++; BkSls[x][N-1+i-j]++;
           if (x==0) Solve(level+1,t,topB);
           else      Solve(level+1,topA,t);
           Map[i][j]=0; Tate[x][j]--; Yoko[x][i]--;
           Slash[x][i+j]--; BkSls[x][N-1+i-j]--;
       }
}

/*┌────────────────────┐
 │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++) Solve(0,0,0);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    for (i=0;i<LogSize;i++) Print(Log[i]);
    return 0;
}