/*
2004/4 カーペンターズ・パズル
coded by Isaku WADA
 ┌──────────────────────────────┐
 │ Fig.1-(a)のように,6×4のマスに9個のコインが置いてある│
 │。これをスタートとして,Fig.1-(b)のようにグレーの部分にコイ│
 │ンをすべて移したい。どのコインも,次の2種類の移動が可能であ│
 │る。                            │
 │ @縦,横,斜め方向の隣のマスが空いていれば1マス進む   │
 │ A縦,横,斜め方向の隣のマスにコインがあって,その先のマス│
 │  が空いていれば1つ飛び越す               │
 │ 1つのコインがこのどちらかの移動を1回行うと「1手」と数え│
 │るとすると,最低何手で移せるだろうか。           │
 │ 当然,1マスに2個以上のコインは入れない。また,コインに区│
 │別はないので,スタート時とゴール時において,9個のコイン同士│
 │の位置関係が同じである必要はない(たとえば,スタート時の中央│
 │のコインが,ゴール時にも中央にある必要はない)。      │
 │                              │
 │Fig.1 カーペンターズ・パズル               │
 │                              │
 │  (a) スタートの配置    (b) ゴールの配置       │
 │    ●●●□□□       □□□●●●       │
 │    ●●●□□□       □□□●●●       │
 │    ●●●□□□       □□□●●●       │
 │    □□□□□□       □□□□□□       │
 │                              │
 └──────────────────────────────┘
 ┌───────────────────────────┐
 │解答:15手                     │
 │                           │
 │●●●□□□ ●□●●□□ □●●●□□ □□●●□□│
 │●●●□□□ ●●●□□□ ●●●□□□ ●●●□□□│
 │●●●□□□ ●●●□□□ ●●●□□□ ●●●●□□│
 │□□□□□□ □□□□□□ □□□□□□ □□□□□□│
 │                           │
 │□□●●□□ □□●●□□ □□●●□□ □□●●□□│
 │□●●□□□ □□●●□□ □□●●□□ □□●●□□│
 │●●●●□□ ●●●●□□ ●●□●●□ □●●●●□│
 │□□●□□□ □□●□□□ □□●□□□ □□●□□□│
 │                           │
 │□□●●□□ □□●●□□ □□●●□□ □□●●□□│
 │□□●●□□ □□●●□□ □□●●□□ □□□●●□│
 │□●●●●□ □●●□●● □□●●●● □□●●●●│
 │□□□●□□ □□□●□□ □□□●□□ □□□●□□│
 │                           │
 │□□●●□□ □□●●●□ □□●●□● □□□●●●│
 │□□□●●● □□□●●● □□□●●● □□□●●●│
 │□□●●●● □□□●●● □□□●●● □□□●●●│
 │□□□□□□ □□□□□□ □□□□□□ □□□□□□│
 │                           │
 └───────────────────────────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │ 実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.05968 秒│ 49152 byte │
 │Microsoft Visual C++ 2003  │0.04078 秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │0.12125 秒│ 54272 byte │
 │gcc-2.953(djgpp)      │0.08187 秒│ 109023 byte │
 │gcc-2.953(cygwin)      │0.08094 秒│ 19905 byte │
 │LSI C-86 Ver 3.30 試食版  │0.19010 秒│ 13932 byte │
 │Turbo C Ver 1.5(small model)│0.17630 秒│ 11544 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP    │
 └──────────────┴─────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ メモリの節約のため深さ優先探索で解きました。盤面の対称性│
 │を利用して、現在盤面と左右対称のものが過去に現れていれば探│
 │索を終了するようにしました。               │
 │ 再帰呼び出しを使って探索します。まず、一番右のコインを除│
 │く全てのコインについて繰り返します。無駄を省くため、その内│
 │側で右上、右、右下の3方向について繰り返します。対象となっ│
 │たコインを選ばれた方向へ動かせれば、動かします。     │
 │ その状態の左右対称のものがあるかどうか確認します。もし、│
 │あれば、左右対称に変換したものをたどってゆけば、終了状態に│
 │なるので、解が見つかったことになります。         │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 今回の問題も LSI-C 86 で解けたので満足です。      │
 └─────────────────────────────┘*/

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

/*┌───────┐
 │定数と型の宣言│
 └───────┘*/
#define N (15/2+1)
typedef char map_t[4][6]; /* 盤の型 */
typedef enum { NORMAL,MIRROR,FINISH } print_mode_t;

/*┌─────┐
 │変数の宣言│
 └─────┘*/
map_t Map;
map_t Log[N+1]=
{{{1,1,1,0,0,0},
  {1,1,1,0,0,0},
  {1,1,1,0,0,0},
  {0,0,0,0,0,0}}};

/*┌────┐
 │盤を書く│
 └────┘*/
void Print(print_mode_t mode,map_t map)
{
    static char buf[4][80]; int i,j; static int col,count,omit;

    if (omit) return;
    if (mode!=FINISH) {
        count++;
        if (col++) for (i=0;i<4;i++) strcat(buf[i]," ");
        for (i=0;i<4;i++) for (j=0;j<6;j++)
         if (map[i][mode==NORMAL?j:5-j]) strcat(buf[i],"●");
         else strcat(buf[i],"□");
    }
    if ((mode==FINISH&&col)||col==4) {
        for (i=0;i<4;i++) { printf("%s\n",buf[i]); buf[i][0]=0; }
        col=0; printf("\n");
    }
    if (mode==FINISH) { printf("%d 手\n", count-1); omit=1; }
}

/*┌──────────┐
 │鏡像かどうか判定する│
 └──────────┘*/
int IsMirror(map_t a,map_t b)
{
    int i,j;

    for (i=0;i<4;i++) for (j=0;j<6;j++)
     if (a[i][j]!=b[i][5-j]) return 0;
    return 1;
}

/*┌─────────────────┐
 │再帰呼び出しをしながら解を探索する│
 │解が見つかったら1以外を返す   │
 └─────────────────┘*/
int Solve(int lv)
{
    int i,j; /* 現在動かそうとしているコインの位置 */
    int s;   /* コインを動かす方向 */
    int u,v; /* コインの移動先の位置 */

    if (lv>N) return 0;

    /* 一番右を除くコインの乗っている盤全てについて繰り返す */
    for (i=0;i<4;i++) for (j=0;j<5;j++) if (Map[i][j])

     /* 3方向について繰り返す */
     for (s=-1;s<=1;s++) {

         u=i+s; v=j+1;
         if (u<0||u>=4||v<0) continue;

         /* 飛び越す場合の処理 */
         if (Map[u][v]) {
             u+=s; v++;
             if (u<0||u>=4||v<0||v>=6||Map[u][v]) continue;
         }

         /* コインを移動する */
         Map[u][v]=1; Map[i][j]=0;

         if (IsMirror(Map,Log[lv-1])) {
             int k; /* 解が見つかったので表示する */

             for (k=0;k<lv;k++)    Print(NORMAL,Log[k]);
             for (k=lv-1;k>=0;k--) Print(MIRROR,Log[k]);
             Print(FINISH,0); return 1;
         }
         memcpy(Log[lv],Map,sizeof Map);
         if (Solve(lv+1)) return 1; /* 再帰呼び出し */

         /* コインを元に戻す */
         Map[u][v]=0; Map[i][j]=1;
     }
    return 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++)
    { memcpy(Map,Log[0],sizeof Map); Solve(1); }
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return EXIT_SUCCESS;
}