/*
2003/04 スライディング・スリー
coded by Isaku WADA
 ┌───────────────────────────┐
 │ Fig.1のように,5×5の盤にA〜Eの計5個のコマが置│
 │いてある。このうち3個のコマを動かして,盤の縦5本横5│
 │本斜め2本の同一直線上に2個以上のコマがこないようにし│
 │たい。1個のコマが移動できるのは1回の直進のみで,タテ│
 │ヨコ・ナナメのどれかの方向に何マス移動してもよい(チェ│
 │スのクイーンの動き)。ほかのコマを飛び越したり,重ねた│
 │りすることはできない。また,3個のコマの移動は同時では│
 │なく,1個ずつ順番に行われる。Fig.1をスタートとして,│
 │どのコマをどのように動かせば完成できるだろうか。   │
 │                           │
 │  Fig.1 スライディング・スリーのコマの初期配置  │
 │       ┌─┬─┬─┬─┬─┐         │
 │       │ │ │ │ │ │         │
 │       ├─┼─┼─┼─┼─┤         │
 │       │ │ │A│ │B│         │
 │       ├─┼─┼─┼─┼─┤         │
 │       │ │ │ │C│D│         │
 │       ├─┼─┼─┼─┼─┤         │
 │       │ │ │ │ │ │         │
 │       ├─┼─┼─┼─┼─┤         │
 │       │ │ │E│ │ │         │
 │       └─┴─┴─┴─┴─┘         │
 └───────────────────────────┘
 ┌────────────┐
 │解答:順番ABD    │
 │・・・・・   ・・・・D│
 │・・A・B   ・B・・・│
 │・・・CD → ・・・C・│
 │・・・・・   A・・・・│
 │・・E・・   ・・E・・│
 └────────────┘
 ┌──────────────┬──────┬───────┐
 │コンパイラ          │実行時間  │ファイルサイズ│
 ├──────────────┼──────┼───────┤
 │Microsoft Visual C++ 6.0    │0.00007234秒│  36864 byte  │
 │Microsoft Visual C++ .NET   │0.00006968秒│  45056 byte  │
 │Borland C++ 5.5.1 for Win32 │0.00008937秒│  54784 byte  │
 │gcc-2.953(djgpp)            │0.00008297秒│ 109564 byte  │
 │gcc-2.953(cygwin)           │0.00008406秒│  20787 byte  │
 │LSI C-86 Ver 3.30 試食版  │0.00020710秒│ 14418 byte │
 │Turbo C Ver 1.5(small model)│0.00021140秒│ 11854 byte │
 ├──────────────┼──────┴───────┤
 │ CPU:Pentium4 2.52GHz  │     OS:Windows XP     │
 └──────────────┴──────────────┘

 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ プログラムは一個のコマの動かし方に対して、3重のループを│
 │構成しています。外側のループは、どのコマを動かすかを決め、│
 │中間のループは8方向のうちのどの方向に動かすかを決め、内側│
 │のループは、どれだけの距離を動かすかを決めています。   │
 │ 一個のコマの動かし方を決める3重ループを、一つの関数の中│
 │に記述し、これを深さ3の再帰呼び出しを行うことで9重ループ│
 │を実現しました。                     │
 │ コマを移動させる9重ループのさらに内側で、問題の条件であ│
 │る「同一直線上に2個以上のコマがこない」をチェックしていま│
 │す。このチェックは関数ではなく、マクロで記述しました。関数│
 │でこれ以上簡素で効率のよいソースを書くことは、不可能である│
 │し、展開して記述すれば、冗長で読みにくいソースになるからで│
 │す。移動結果がこの条件をパスしたら、画面にコマの順番と終了│
 │状態を表示して、再帰呼び出しの関数を全て終了して、プログラ│
 │ムも終了します。                     │
 │ 1回の探索では短すぎてプログラムの実行時間の計測はできま│
 │せん。そこで、探索を十万回繰り返し、1回あたりの平均値を求│
 │めることにより実行時間を得ました。            │
 │ Turbo C などの clock() がないコンパイラのために clock() │
 │を自作してあります。また、LSI-C86 のように、clock() が1秒│
 │単位でしか時間を返さないものでも100分の1秒単位で計測で│
 │きるようになります。この自作の clock() は、マクロ     │
 │CLOCKS_PER_SEC が1以外に定義されていれば、自動的に無視さ │
 │れます。                         │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 与えられた配置の場合、運よく、探索の最初のほうで解が見つ│
 │かり、すぐにプログラムが終了しました。比較のため、全探索を│
 │行った場合、どの位時間がかかるかを計測したところ、約37倍│
 │時間がかかりました。                   │
 └─────────────────────────────┘

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

#define N        5 /* 盤の一辺の長さ、と同時に、コマの数 */
#define MOVE     3 /* 何個移動させるか                   */
#define ENUM_ALL 0 /* これを0以外にすると全探索する     */

char Start[N][N+1]= /* 初期配置 */
{"     ",
 "  A B",
 "   CD",
 "     ",
 "  E  "};
int FromX[N],FromY[N]; /* コマの初期位置 */
int Order[MOVE]; /* 順番。例えば、ABDの順に動かすならなら{0,1,3}*/
int PrintMode;   /* 0なら非表示。0以外なら表示 */
int NumOfSol;    /* 解の数 */

/* 解の表示 */
void Print(char map[][N+1])
{
    int i,j,move,counter; static char alpha[]=
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    /* 順番の表示 */
    printf("No.%d 順番",NumOfSol);
    for (move=0;move<MOVE;move++)
     for (counter=i=0;i<N;i++) for (j=0;j<N;j++)
      if (Start[i][j]!=' ') if (counter++==Order[move])
      { printf("%.2s",alpha+(Start[i][j]-'A')*2); break; }
    printf("\n");
    for (i=0;i<N;i++) {
        /* 初期配置の表示 */
        for (j=0;j<N;j++)
         if (Start[i][j]==' ') printf("・");
         else printf("%.2s",alpha+(Start[i][j]-'A')*2);
        if (i==(N-1)/2) printf(" → "); else printf("   ");
        /* 移動後の配置の表示 */
        for (j=0;j<N;j++)
         if (map[i][j]==' ') printf("・");
         else printf("%.2s",alpha+(map[i][j]-'A')*2);
        printf("\n");
    }
    printf("\n");
}

/* 直線上に2コマ以上並ぶと break するマクロ */
/* A:直線の数    B:直線の長さ   (Y,X) 座標   */
#define CHECK(A,B,Y,X)                               \
    for (i=A-1;i>=0;i--) {                           \
        for (k=0,j=B-1;j>=0;j--) if (map[Y][X]!=' ') \
        { if (k) break; else k=1; }                  \
        if (j>=0) break;                             \
    }                                                \
    if (i>=0) break;

/* メインループ(解が見つかれば1を返す) */
int Loop(int level,char map[][N+1],int dirX[],int dirY[])
{
    int p,dir,dx,dy,k; /* コマと方向と座標値の増分と汎用 */
    unsigned fx,fy,x,y; char ch; /* 移動元と移動先と文字 */

    for (p=0;p<N;p++) { /* コマを選ぶ */
        for (k=0;k<level;k++) if (Order[k]==p) break;
        if (k<level) continue; /* 同じコマを選んだらスキップ */
        Order[level]=p; fx=FromX[p]; fy=FromY[p]; ch=map[fy][fx];
        for (dir=0;dir<8;dir++) { /* 8方向繰り返す */
            x=fx; y=fy; dx=dirX[dir]; dy=dirY[dir];
            for (;;) {
                x+=dx; y+=dy; /* コマを一歩進める */
                /* 外に出たり、他と重なれば抜ける */
                if (x>=N||y>=N||map[y][x]!=' ') break;
                map[y][x]=ch; map[fy][fx]=' '; /* 移動する */
                if (level==MOVE-1)
                 for (;;) {
                     int i,j;
                     CHECK(N,N,i,j)               /* = */
                     CHECK(N,N,j,i)               /* ll */
                     CHECK(N-1,i+2,j,1+i-j)       /*'/ */
                     CHECK(N-2,i+2,N-2+j-i,N-1-j) /* /.*/
                     CHECK(N-1,i+2,j,N-2-i+j)     /* \'*/
                     CHECK(N-2,i+2,N-1-j,1+i-j)   /*.\ */
                     NumOfSol++;
                     if (PrintMode) Print(map);
#if ENUM_ALL != 0
                     break;
#else
                     return 1;
#endif
                 } else if (Loop(level+1,map,dirX,dirY)) return 1;
                map[fy][fx]=ch; map[y][x]=' '; /* 移動を元に戻す */
            }
        }
    }
    return 0;
}

/* パズルを解く(引数が0以外なら解答を表示) */
void Solve(int prn)
{
    int dirX[]={-1,-1, 0,1,0,-1,1, 1}; /* 方向の横増分 */
    int dirY[]={ 1, 0,-1,0,1,-1,1,-1}; /* 方向の縦増分 */
    int k,i,j;  char map[N][N+1]; /* 作業用 */

    PrintMode=prn; NumOfSol=0;
    /* map[][],FromX[],FromY[] の設定 */
    memcpy(map,Start,sizeof map);
    for (k=i=0;i<N;i++) for (j=0;j<N;j++)
     if (map[i][j]!=' ') { FromX[k]=j; FromY[k]=i; k++; }
    Loop(0,map,dirX,dirY);
}

/* 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(); long i,num;

    if (argc==2) num=atol(argv[1]); else num=1;
    for (i=0;i<num;i++) Solve(i==0);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}