过河问题，可撑船三人：老人，丈夫，妻子; 乘客五位：两男孩，两女孩，一只狗; 条件：A.一条可乘两人的船; B.狗没有老人看管的情况下会咬人, C:妻子不在场，丈夫会打女孩;D.丈夫不在场，妻子会打男孩；问题：请问船过河多少次可以全员由河的左岸到达右岸？

pass_river_puzzle.c

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

typedef enum live {
    placeholder,
    oldman,
    dog,
    husband,
    wife,
    boy,
    girl,
    kinds,
} live;

struct side {
    int flag;
    int n;
    int data[kinds];
};

const char *livename[] = {
    "",
    "oldman",
    "dog",
    "husband",
    "wife",
    "boy",
    "girl",
};

struct side left, right;
struct side lefthistory[40], righthistory[40];
int leftmark = 0, rightmark = 0;
int round;

live group[] = {
    oldman, dog, 
    oldman, boy,
    oldman, girl,
    wife, girl,
    husband, boy,
    wife, oldman,
    husband, oldman,
    husband, wife,
    husband, placeholder,
    oldman, placeholder,
    wife, placeholder,
};

int groupsize = sizeof(group) / 2 / sizeof(live);



int checkside(struct side *s)
{
    if (s->data[oldman] == 0
        && s->n > 1
        && s->data[dog] == 1) return 0;

    if (s->data[husband] == 0
        && s->data[wife] == 1
        && s->data[boy] > 0) return 0;

    if (s->data[husband] == 1
        && s->data[wife] == 0
        && s->data[girl] > 0) return 0;

    return 1;
}

int isferryman(live l)
{
    return l == oldman
        || l == husband
        || l == wife;
}

void onboat(struct side *side, live ferryman, live host) 
{
    --side->data[ferryman];
    --side->n;
    if (host != placeholder) {
        --side->data[host];
        --side->n;
    }
}

void downboat(struct side *side, live ferryman, live host)
{
    ++side->data[ferryman];
    ++side->n;
    if (host != placeholder) {
        ++side->data[host];
        ++side->n;
    }
}

void printside(struct side *side)
{
    printf("side:%d, n=%d, oldman=%d, dog=%d, husband=%d, wife=%d, boy=%d, girl=%d\n"
            , side->flag, side->n, side->data[oldman], side->data[dog], side->data[husband], side->data[wife], side->data[boy], side->data[girl]);
}

int compareside(struct side *a, struct side *b)
{
    if (a->flag != b->flag) return 0;
    if (a->n != b->n) return 0;

    if (a->data[oldman] != b->data[oldman]) return 0;
    if (a->data[dog] != b->data[dog]) return 0;
    if (a->data[husband] != b->data[husband]) return 0;
    if (a->data[wife] != b->data[wife]) return 0;
    if (a->data[girl] != b->data[girl]) return 0;
    if (a->data[boy] != b->data[boy]) return 0;

    return 1;
}

int checkhistory(struct side *side)
{
    int i = 0, n; 
    struct side *history;
    if (side->flag) {
        history = righthistory;
        n = rightmark;
    }
    else {
        history = lefthistory;
        n = leftmark;
    }

    for(; i < n; i++) {
        if (compareside(side, &history[i])) return 0;
    }

    return 1;
}

int checkload(struct side *start, live ferryman, live host)
{
    if (start->data[ferryman] <= 0) return 0;
    if (host != placeholder 
        && start->data[host] <= 0) return 0;
    return 1;
}

int gothrough(struct side *start, struct side *end, int flag)
{
    /*if (left.n == 0 && right.n == 8) return 1;*/
    if (flag == 1 && end->n == 0) return 1;


    live ferryman, host;

    int i, z, s;
    if (flag) {
        i = groupsize - 1;
        z = -1;
        s = -1;
    }
    else {
        i = 0;
        z = groupsize;
        s = 1;
    }

    for(; i != z; i+=s) {
        if (isferryman(group[i * 2])) {
            ferryman = group[i * 2];
            host = group[i * 2 + 1];

            if (!checkload(start, ferryman, host)) continue;

            onboat(start, ferryman, host);
            downboat(end, ferryman, host);

            // if pass
            if (checkside(start) && checkside(end)) {

                if (checkhistory(start)) {

                    if (flag) {
                        righthistory[rightmark++] = *start;
                    }
                    else {
                        lefthistory[leftmark++] = *start;
                    }

                    if (gothrough(end, start, flag == 0 ? 1 : 0)) {
                        printf("round:%d left%s---%sright, ferryman:%s, host:%s\n"
                                , ++round
                                , start->flag ? "<" : ""
                                , start->flag ? "" : ">"
                                , livename[ferryman], livename[host]);
                        return 1;
                    }
                }
            }

            // return boat
            onboat(end, ferryman, host);
            downboat(start, ferryman, host);

        } 
    }

    return 0;
}

void initdata()
{
    round = 0;

    left.flag = 0;
    left.n = 8;

    left.data[placeholder] = 0;
    left.data[oldman] = 1;
    left.data[dog] = 1;
    left.data[husband] = 1;
    left.data[wife] = 1;
    left.data[boy] = 2;
    left.data[girl] = 2;

    memset(&right, 0, sizeof(right));
    right.flag = 1;
}

void start()
{
    initdata();

    printf("original data:\n");
    printside(&left);
    printside(&right);

    printf("begin puzzle:\n");
    if (gothrough(&left, &right, 0)) {
        printf("finished data:\n");
    }
    else {
        printf("fail data:\n");
    }

    printside(&left);
    printside(&right);
}


int main(void)
{
    start();

    return 0;
}

pass_river_puzzle.lua

local live = {
    "oldman",
    "dog",
    "husband",
    "wife",
    "boy",
    "girl",
}

local group = {
    "oldman", "dog", 
    "oldman", "boy",
    "oldman", "girl",
    "wife", "girl",
    "husband", "boy",
    "wife", "oldman",
    "husband", "oldman",
    "husband", "wife",
    "husband", false,
    "oldman", false,
    "wife", false, 
}

local round = 0
local left, lefthistory, right, righthistory = {}, {}, {}, {}

local function print_side(side)
    print(string.format("side:%d, n=%d, oldman=%d, dog=%d, husband=%d, wife=%d, boy=%d, girl=%d"
            , side.flag and 1 or 0, side.n, side.oldman, side.dog, side.husband, side.wife, side.boy, side.girl))
end

local function isferryman(live)
    return live == "oldman" or live == "wife" or live == "husband"
end

local function checkload(side, ferryman, host)
    if side[ferryman] <= 0 then return false end
    if side[host] ~= nil and side[host] <=0 then return false end
    return true
end

local function checkside(side)
    if side.oldman == 0
        and side.n > 1
        and side.dog == 1 then
        return false
    end

    if side.husband == 0
        and side.wife == 1
        and side.boy > 0 then
        return false
    end

    if side.husband == 1
        and side.wife == 0
        and side.girl > 0 then
        return false
    end

    return true
end


local function compareside(a, b)
    for k, v in pairs(a) do
        if a[k] ~= b[k] then return false end 
    end

    return true
end


local function checkhistory(side)
    local history = side.flag and righthistory or lefthistory

    for i = 1, #history do
        if compareside(side, history[i]) then return false end
    end

    return true
end

local function copyside(side)
    local target = {}
    for k, v in pairs(side) do
        target[k] = v
    end

    return target
end

local function onboat(side, ferryman, host)
    side[ferryman] = side[ferryman] - 1
    side.n = side.n - 1
    if host then
        side[host] = side[host] - 1
        side.n = side.n - 1
    end
end

local function downboat(side, ferryman, host)
    side[ferryman] = side[ferryman] + 1
    side.n = side.n + 1
    if host then
        side[host] = side[host] + 1
        side.n = side.n + 1
    end
end

local function gothrough(startside, endside, flag)
    if flag and endside.n == 0 then return true end

    local ferryman, host

    local i, z, s
    if flag then
        i = #group - 1
        z = 1
        s = -2
    else
        i = 1
        z = #group
        s = 2
    end

    for i = i, z, s do
        if isferryman(group[i]) then
            ferryman = group[i]
            host = group[i + 1]

            if checkload(startside, ferryman, host) then
                onboat(startside, ferryman, host)
                downboat(endside, ferryman, host)

                if checkside(startside) and checkside(endside) then

                    if checkhistory(startside) then
                        if flag then
                            righthistory[#righthistory + 1] = copyside(startside)
                        else
                            lefthistory[#lefthistory + 1] = copyside(startside)
                        end

                        if gothrough(endside, startside, not flag) then
                            round = round + 1
                            print(string.format("round:%d left%s--%sright, ferryman:%s, host:%s"
                            , round
                            , startside.flag and "<" or ""
                            , startside.flag and "" or ">"
                            , ferryman
                            , host or ""))
                            return true
                        end
                    end
                end

                onboat(endside, ferryman, host)
                downboat(startside, ferryman, host)

            end
        end
    end

end

local function init_data()

    left.n = 8
    left.flag = false

    right.n = 0
    right.flag = true

    for _, v in ipairs(live) do
        left[v], right[v] = 1, 0
    end
    left.boy = 2
    left.girl = 2

end

local function start()
    init_data()

    print("orginal data:")
    print_side(left)
    print_side(right)

    print("begin puzzle:")
    if gothrough(left, right, false) then
        print("finished data:")
    else
        print("fail puzzle!")
    end

    print_side(left)
    print_side(right)
end

local function main()
    start()
end

main()