/************************************************************/
/* ブラックボックス                     2002/08/15  takaken */
/************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 0:オリジナルルール 1:majorさん独自ルール
#define  ROULE  0

//////////////////////////////////////////////////////////////
#define  FALSE  0
#define  TRUE   1

#define  BOARD_SIZE 100
#define  BALL        33
#define  XX          34

// ボールの個数
int  BALL_CNT;

// 探索ボード
int  BOARD[BOARD_SIZE] = {
   XX,32,31,30,29,28,27,26,25,XX,
    1, 0, 0, 0, 0, 0, 0, 0, 0,24,
    2, 0, 0, 0, 0, 0, 0, 0, 0,23,
    3, 0, 0, 0, 0, 0, 0, 0, 0,22,
    4, 0, 0, 0, 0, 0, 0, 0, 0,21,
    5, 0, 0, 0, 0, 0, 0, 0, 0,20,
    6, 0, 0, 0, 0, 0, 0, 0, 0,19,
    7, 0, 0, 0, 0, 0, 0, 0, 0,18,
    8, 0, 0, 0, 0, 0, 0, 0, 0,17,
   XX, 9,10,11,12,13,14,15,16,XX
};

// 光の入出力テーブル
int  PROB_CNT;
int  INP[32], OUT[32];

// 解の記録
int  RESULT;
int  RECORD[BOARD_SIZE];

// 方向テーブル(座標変位)
int  DIFF[8] = {-10,-9, 1,11,10, 9,-1,-11};

// 入出力ナンバー -> 座標
int  POS[33] = { 0,
    10,20,30,40,50,60,70,80,
    91,92,93,94,95,96,97,98,
    89,79,69,59,49,39,29,19,
     8, 7, 6, 5, 4, 3, 2, 1
};

// 入出力ナンバー -> 初期進行向き
int  VECT[33] = { 0,
    2,2,2,2,2,2,2,2,
    0,0,0,0,0,0,0,0,
    6,6,6,6,6,6,6,6,
    4,4,4,4,4,4,4,4
};

// 反復深化用
int  MAX_DEPTH;
int  USED[33];

/************************************************************/
/* 解の表示                                                 */
/************************************************************/
void Display(void)
{
    int  pos;

    for (pos=0; pos<BOARD_SIZE; pos++) {
        if (pos && !(pos % 10)) printf("\n");
        switch (RECORD[pos]) {
            case 0:    printf(" 口"); break;
            case XX:   printf("   "); break;
            case BALL: printf(" ●"); break;
            default:   printf(" %2d", RECORD[pos]);
        }
    }
    printf("\n");
}
/************************************************************/
/* ブラックボックスソルバー                                 */
/************************************************************/
// 解の記録と重複チェック
void Record(void)
{
    int  pos;

    if (RESULT == 0) {
        RESULT = 1;
        for (pos=0; pos<BOARD_SIZE; pos++)
            RECORD[pos] = BOARD[pos];
    } else {
        for (pos=0; pos<BOARD_SIZE; pos++)
            if (RECORD[pos] != BOARD[pos]) break;
        if (pos < BOARD_SIZE) RESULT = 2; // 重複あり(解を特定出来ない)
    }
}
// オリジナルルールチェック
int  Check1(void)
{
    int  i, pos, pos1, pos2, vect, inp, out, cnt;

    // 優先順位 b:ボール吸収, e:入口反射, d:180度反射, c:90度転換, a:直進
    for (i=0; i<PROB_CNT; i++) {
        inp  = INP[i];
        out  = OUT[i];
        vect = VECT[inp];
        pos  = POS[inp] + DIFF[vect];

        // ルール(b:ボール吸収)
        if (BOARD[pos] == BALL) {
            if (out != 0) return FALSE;
            continue;
        }

        // ルール(e:入口反射)
        pos1 = pos + DIFF[(vect + 2) % 8];
        pos2 = pos + DIFF[(vect + 6) % 8];
        if (BOARD[pos1]==BALL || BOARD[pos2]==BALL) {
            if (out != inp) return FALSE;
            continue;
        }

        for (cnt=0; cnt<256 && !BOARD[pos]; cnt++) {
            pos1 = pos + DIFF[(vect + 1) % 8];
            pos2 = pos + DIFF[(vect + 7) % 8];

            // ルール(d:180度反射)
            if (BOARD[pos1]==BALL && BOARD[pos2]==BALL) {
                vect = (vect + 4) % 8;
            } else

            // ルール(c:90度転換)
            if (BOARD[pos1] == BALL) {
                vect = (vect + 6) % 8;
            } else
            if (BOARD[pos2] == BALL) {
                vect = (vect + 2) % 8;
            }

            pos += DIFF[vect];
        }
        if (cnt == 256)     {           // ループ吸収
            if (out != 0) return FALSE;
        } else {
            if (BOARD[pos] == BALL) {   // ボール吸収
                if (out != 0) return FALSE;
            } else {                    // 出口
                if (out != BOARD[pos]) return FALSE;
            }
        }
    }
    return TRUE;
}
// majorさん独自ルールチェック
int  Check2(void)
{
    int  i, pos, pos1, pos2, vect, inp, out;

    // 優先順位 b:ボール反射, e:入口反射, d:180度反射, c:90度転換, a:直進
    for (i=0; i<PROB_CNT; i++) {
        inp  = INP[i];
        out  = OUT[i];
        vect = VECT[inp];
        pos  = POS[inp] + DIFF[vect];

        // ルール(b:ボール反射)
        if (BOARD[pos] == BALL) {
            if (out != inp) return FALSE;
            continue;
        }

        // ルール(e:入口反射)
        pos1 = pos + DIFF[(vect + 2) & 7];
        pos2 = pos + DIFF[(vect + 6) & 7];
        if (BOARD[pos1]==BALL || BOARD[pos2]==BALL) {
            if (out != inp) return FALSE;
            continue;
        }

        for (;;) {
            if (BOARD[pos]) {
                // ルール(b:ボール反射)
                if (BOARD[pos] == BALL) {
                    vect = (vect + 4) & 7;
                    pos += DIFF[vect];
                    continue;
                } else break; // 出口
            }

            pos1 = pos + DIFF[(vect + 1) & 7];
            pos2 = pos + DIFF[(vect + 7) & 7];

            // ルール(d:180度反射)
            if (BOARD[pos1]==BALL && BOARD[pos2]==BALL) {
                vect = (vect + 4) & 7;
            } else

            // ルール(c:90度転換)
            if (BOARD[pos1] == BALL) {
                vect = (vect + 6) & 7;
            } else
            if (BOARD[pos2] == BALL) {
                vect = (vect + 2) & 7;
            }

            pos += DIFF[vect];
        }
        // 出口
        if (out != BOARD[pos]) return FALSE;
    }
    return TRUE;
}
// 総てのボール配置パターンを生成する
void Backtrack(int pos, int count)
{
    if (count == BALL_CNT) {
#if !ROULE
        if (Check1()) Record(); // オリジナルルール
#else
        if (Check2()) Record(); // majorさん独自ルール
#endif
    } else {
        for ( ; pos<BOARD_SIZE; pos++) {
            if (BOARD[pos]) continue;
            BOARD[pos] = BALL;
            Backtrack(pos+1, count+1);
            BOARD[pos] = 0;
            if (RESULT == 2) break;
        }
    }
}
// ブラックボックスソルバー
int  Solver(int prob)
{
    PROB_CNT = prob;    // データの個数

    RESULT = 0;
    Backtrack(0, 0);
    return RESULT; // 0:解がない 1:解を特定出来る 2:解を特定出来ない
}
/************************************************************/
/* ミニマックス法を反復深化で実行                           */
/************************************************************/
int  MinMax(int depth)
{
    int inp, out, end, retc;

    // 深さ制限に達したので探索を打ち切る(解を特定出来ない)
    if (depth == MAX_DEPTH) return FALSE;

    // 解答者レベル(解を特定出来る入口を探す)
    end = depth? 32: 4;
    for (inp=1; inp<=end; inp++) {
        if (USED[inp]) continue;
        INP[depth] = inp;   // 入口データセット

        // 返答者レベル(解を特定出来ない出口を探す)
        for (out=ROULE; out<=32; out++) {
            if (USED[out]) continue;
            OUT[depth] = out;   // 出口データセット

            // 解を特定出来ない出口であるか調べる
            if (Solver(depth+1) != 2) continue;

            // ここで解を特定出来ないならさらに再帰で調べる
            USED[inp] = TRUE;
            if (out && out!=inp) USED[out] = TRUE;
            retc = MinMax(depth+1);
            USED[inp] = FALSE;
            if (out && out!=inp) USED[out] = FALSE;

            // この出口だと解を特定出来ないと判明(返答者は目的を達成)
            if (!retc) break;
        }
        // この入口だとどんな返答でも解を特定出来る(解答者は目的を達成)
        if (out > 32) return inp;
    }
    return FALSE;
}
int BlackBox(int already)
{
    int  inp, retc;

    // 現状を調査する
    retc = Solver(already);
    if (retc == 0) return -1;
    if (retc == 1) return  0;

    // 反復深化
    for (MAX_DEPTH=already+1; ; MAX_DEPTH++) {
        printf("%d ", MAX_DEPTH);
        inp = MinMax(already);
        if (inp) break;
    }
    printf("\n");

    return inp;
}
/************************************************************/
/* インターフェース                                         */
/************************************************************/
int main(void)
{
    int  already, retc;
    time_t  st = time(NULL);

    // ボールの個数
    BALL_CNT = 5;

    // 既に入射した回数とその入口と出口
    already  = 13;
    INP[ 0]= 2; OUT[ 0]= 0;
    INP[ 1]= 4; OUT[ 1]= 0;
    INP[ 2]= 6; OUT[ 2]=14;
    INP[ 3]=15; OUT[ 3]=15;
    INP[ 4]=17; OUT[ 4]= 0;
    INP[ 5]=18; OUT[ 5]= 0;
    INP[ 6]=19; OUT[ 6]=19;
    INP[ 7]=25; OUT[ 7]=21;
    INP[ 8]=26; OUT[ 8]=26;
    INP[ 9]=27; OUT[ 9]= 0;
    INP[10]=28; OUT[10]=28;
    INP[11]=29; OUT[11]= 0;
    INP[12]=30; OUT[12]= 0;

    // 探索と結果表示
    retc = BlackBox(already);
    switch (retc) {
        case -1:
            printf("解がありません.\n"); break;
        case  0:
            printf("解が見つかりました.\n");
            Display();
            break;
        default:
            printf("次の%d手目は位置%dに光を当てて下さい.\n", already+1, retc);
            printf("最短%d手以内に解が見つかります.(%dsec)\n", MAX_DEPTH, time(NULL)-st);
    }

    return 0;
}