パズルを解く２

■ パズルを解く２

/*
 *  ship.c : パズルを解く２
 *
 *      Copyright (c) 2001, 2003 AOK.
 *
 *          2001.05.23 - 初版
 *          2001.07.08 - ２版
 *
 *  大きな川があり、一艘の船がある。左岸には男が３人と女が
 *  ３人いる。全員が右岸に渡らなければならない。船には一度
 *  に２人までしか乗れない。男女とも船の運転ができる。しか
 *  し女より男の人数が多いと女は男たちに殺されてしまう。
 *
 */

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

#define MAX_M   3   /* 男性の人数 */
#define MAX_F   3   /* 女性の人数 */

typedef struct _NODE {
    int no;           /* ノードの深さ */
    int m1, f1;       /* 左岸の男女の数 */
    int m2, f2;       /* 右岸の男女の数 */
    struct _NODE *nd; /* 次ノードのアドレス */
} NODE;

NODE f = { 0,MAX_M,MAX_F,0,0,NULL }; /* 最初のノード */

/* 女性が男性と同数か多いとき真 */
#define isok(n) ( ((n->f1==0)||(n->f1>=n->m1))  \
                &&((n->f2==0)||(n->f2>=n->m2)) )

/* 遡ってノードに同じ状態がないとき真（ループ回避） */
int hist(NODE *n)
{
    NODE *p = &f;
    while (p->nd != NULL) {
        if (   (n->no % 2 == p->no % 2)
            && (p->m1 == n->m1)
            && (p->f1 == n->f1) )
                return 0;
        p = p->nd;
    }
    return 1;   
}

/* 最初からの手順を表示 */
void display(void)
{
    NODE *p = &f; int i;
    do {
        printf("(%2d) ", p->no);
        for (i=0; i<p->m1; i++) printf("●");
        for (i=0; i<p->f1; i++) printf("○");
        if (p->no % 2) printf(" → "); else printf(" ← ");
        for (i=0; i<p->m2; i++) printf("●");
        for (i=0; i<p->f2; i++) printf("○");
        putchar('\n');
        p = p->nd;
    } while (p != NULL);
    putchar('\n');
}

/* 船で移動（バックトラック法）*/
void turn(NODE *n)
{
    int i, j;
    NODE *p = (NODE *)calloc(1, sizeof(NODE)); /* 次ノード用のメモリを確保 */
    p->no = n->no + 1; n->nd = p;
    if (p->no % 2) { /* 左岸→右岸 */
        for (i=0; i<=n->m1; i++) { /* 乗船パターン */
            for (j=0; j<=n->f1; j++) {
                if (i+j == 0) continue; if (i+j > 2) break;
                p->m1 = n->m1 - i; p->f1 = n->f1 - j;
                p->m2 = n->m2 + i; p->f2 = n->f2 + j;
                if ((p->m2 == MAX_M) && (p->f2 == MAX_F)) {
                    display(); /* 右岸へ渡りきった */
                } else {
                    if (isok(p) && hist(p)) turn(p);
                }
            }
        }
    } else { /* 左岸←右岸 */
        for (i=0; i<=n->m2; i++) { /* 乗船パターン */
            for (j=0; j<=n->f2; j++) {
                if (i+j == 0) continue; if (i+j > 2) break;
                p->m2 = n->m2 - i; p->f2 = n->f2 - j;
                p->m1 = n->m1 + i; p->f1 = n->f1 + j;
                if (isok(p) && hist(p)) turn(p);
            }
        }
    }
    n->nd = NULL;
    free(p); /* 確保したメモリを解放 */
}

/* メインルーチン */
int main(void)
{
    turn(&f); /* 移動開始 */
    return 0;
}

/* --- 実行結果 -------------------------------------

( 0) ●●●○○○ ← 
( 1) ●●○○ → ●○
( 2) ●●○○○ ← ●
( 3) ○○○ → ●●●
( 4) ●○○○ ← ●●
( 5) ●○ → ●●○○
( 6) ●●○○ ← ●○
( 7) ●● → ●○○○
( 8) ●●● ← ○○○
( 9) ● → ●●○○○
(10) ●○ ← ●●○○
(11)  → ●●●○○○

( 0) ●●●○○○ ← 
( 1) ●●○○ → ●○
( 2) ●●○○○ ← ●
( 3) ○○○ → ●●●
( 4) ●○○○ ← ●●
( 5) ●○ → ●●○○
( 6) ●●○○ ← ●○
( 7) ●● → ●○○○
( 8) ●●● ← ○○○
( 9) ● → ●●○○○
(10) ●● ← ●○○○
(11)  → ●●●○○○

( 0) ●●●○○○ ← 
( 1) ●○○○ → ●●
( 2) ●●○○○ ← ●
( 3) ○○○ → ●●●
( 4) ●○○○ ← ●●
( 5) ●○ → ●●○○
( 6) ●●○○ ← ●○
( 7) ●● → ●○○○
( 8) ●●● ← ○○○
( 9) ● → ●●○○○
(10) ●○ ← ●●○○
(11)  → ●●●○○○

( 0) ●●●○○○ ← 
( 1) ●○○○ → ●●
( 2) ●●○○○ ← ●
( 3) ○○○ → ●●●
( 4) ●○○○ ← ●●
( 5) ●○ → ●●○○
( 6) ●●○○ ← ●○
( 7) ●● → ●○○○
( 8) ●●● ← ○○○
( 9) ● → ●●○○○
(10) ●● ← ●○○○
(11)  → ●●●○○○

 ------------------------------------------------- */
■ パズルを解く ２

■ パズルを解く２
