/*
 *  family.c : パズルを解く（再帰を利用）
 *
 *  Copyright (c) 2000, 2001 AOK. 
 *  
 *      2000.9.14 - ４版
 *      2001.5.21 - ７版（全パターンを出力するように修正）
 *      2001.5.24 - ９版（素数の性質を利用したものに変更）
 *
 * ある家族、父、母、娘が２人、息子が２人、召使い、犬がいます。
 * この家族が大きな川を渡ろうとしています。船は一つしかありませ
 * ん。しかも乗れるのは２人だけで一人は運転手がいります。運転出
 * 来るのは、父、母、召使いだけです。父は母がいないと息子を殺し、
 * 母は父がいないと娘を殺し、犬は召使いがいないと家族を殺します。
 * どうしたら川を渡れるかな？ 何回往復してもいい。 
 *
 */

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

#define numof(x)    (sizeof(x)/sizeof(x[0]))

#define FT   2
#define MT   3
#define SN   5
#define DT   7
#define SL  11
#define DG  13

#define AL  (FT*MT*SN*SN*DT*DT*SL*DG) /* (家族全員) */

typedef struct _STAT {
    int no;     /* ステージ数 */
    long here;  /* 此岸 */
    long ship;  /* 船上 */
    long there; /* 対岸 */
    struct _STAT *next;
} STAT;

/* 最初の此岸・船上・対岸の状態 */
STAT start = { 0, AL, 1, 1, NULL };

const long pt[] = { /* 船上パターン */
    FT   , MT   , SL   , FT*MT, FT*DT,
    FT*SL, MT*SN, MT*SL, SL*SN, SL*DT,
    SL*DG,
};

/* 状態の表示用 */
void output(long s)
{
    if (s % FT == 0) printf("父"); if (s % MT == 0) printf("母");
    if (s % SN == 0) printf("息"); if (s % (SN*SN) == 0) printf("息");
    if (s % DT == 0) printf("娘"); if (s % (DT*DT) == 0) printf("娘");
    if (s % SL == 0) printf("召"); if (s % DG == 0) printf("犬");
}

/* すべての条件の判定 */
int ok(long s)
{
    /* 父は母がいないと息子達を殺す */
    if (!(s % (FT*SN)) && (s % MT)) return 0;
    /* 母は父がいないと娘達を殺す */
    if (!(s % (MT*DT)) && (s % FT)) return 0;
    /* 犬は召使いがいないと家族を殺す */
    if (!(s % DG) && (s % SL) && (s != DG)) return 0;
    return 1;
}

/* 履歴のパターンと照合 */
int history(STAT *t)
{
    STAT *p = &start;
    while (p->next != NULL) {
        if (t->no % 2) { if (p->here == t->here) return 0; }
        else { if (p->there == t->there) return 0; }
        p = p->next;
    }
    return 1;
}

int check(STAT *t)
{
    if (t->no % 2)
        return (ok(t->here) && ok(t->there * t->ship) && history(t));
    return (ok(t->there) && ok(t->here * t->ship) && history(t));
}

void listout(void)
{
    STAT *p = &start;
    int c;
    do {
        c = p->no % 2;
        printf("(%2d) ", p->no); output(p->here);
        if (c) printf("→"); else printf("←");
        putchar('['); output(p->ship); putchar(']');
        if (c) printf("→"); else printf("←");
        output(p->there); putchar('\n');
        p = p->next;
    } while (p != NULL);
    putchar('\n');
}

/* 船で輸送（再帰関数） */
void shipping(STAT *p)
{
    int i;
    STAT *t = (STAT *)calloc(1, sizeof(STAT));
    t->no = p->no + 1;
    if (t->no % 2) { /* 此岸 → 船 */
        for (i=0; i<numof(pt); i++) {
            t->here = p->here * p->ship;
            t->there = p->there;
            if (t->here % pt[i] == 0) {
                t->here /= pt[i]; t->ship = pt[i];
                if (check(t)) { p->next = t; shipping(t); }
            }
        }
    } else { /* 船 ← 対岸 */
        for (i=0; i<numof(pt); i++) {
            t->there = p->there * p->ship;
            t->here = p->here;
            if (t->there == AL) { /* 家族全員が対岸 */
                listout(); break;
            }
            if (t->there % pt[i] == 0) {
                t->there /= pt[i]; t->ship = pt[i];
                if (check(t)) { p->next = t; shipping(t); }
            }
        }
    }
    p->next = NULL;
    free(t);
}

/* メインルーチン */
int main()
{
    shipping(&start); /* 輸送開始 */
    return 0;
}