不限语言解决“三狼三羊过河问题”

=info
    Farmer across river problem
    523066680/vicyang
    2019-03
    0. 过对岸时，狼+羊至少要有1个（不做无用功）
    1. 返程不应该载羊，因为把羊送过去是首要任务。
    2. 对岸羊 > 狼 时，不需要返回狼。
    3. 对岸数量的历史记录不应该重复（可以消除冗余的过程和结果）。
=cut

my @arr = (1,3,3);
my @brr = (0,0,0);
my $space = 2;  # 船的空位，不包括人
my @op;

main([@arr], [@brr], 0, join(",", @brr), \@op);

sub main
{
    my ($a, $b, $lv, $bhistory, $op ) = @_;

    my $h = 1;
    my ( $w_min, $w_max, $s_min, $s_max );
    my $rest;

    if ( $lv % 2 == 0) {
        $w_min = 0;
        $w_max = $a->[1] > $space ? $space : $a->[1];
        for my $w ( $w_min .. $w_max )
        {
            $rest = $space - $w;
            $s_min = $w == 0 ? 1 : 0;  # 确保不会空船渡河
            $s_max = $a->[2] > $rest ? $rest : $a->[2];
            for my $s ( $s_min .. $s_max )
            {
                push @op, [$h, $w, $s];
                cross( $a, $b, $h, $w, $s, $lv, $bhistory, $op );
                pop @op;
            }
        }
    } else {
        $s = 0; # 羊：回去是不可能回去的，只有在对岸才能够生活这样子。
        $w_min = 0;
        $w_max = $b->[2] > $b->[1] ? 0 : 
                 $b->[2] > $space ? $space : $b->[2] ; # 如果对岸 羊>狼 则狼不必返回
        for my $w ( $w_min .. $w_max )
        {
            push @op, [$h, $w, $s];
            cross( $b, $a, $h, $w, $s, $lv, $bhistory, $op );
            pop @op;
        }
    }
}

sub cross
{
    my ($a, $b, $h, $w, $s, $lv, $bhistory, $op) = @_;

    cross_river($a, $b, [$h,$w,$s]);
    my $chk = $lv % 2 == 0 ? check($a, $b) : check($b, $a);
    # 过河后的状态
    my $curr_a = join(",", @$a);
    my $curr_b = join(",", @$b);
    if ($chk == 1) {
        if ( $lv % 2 == 0 ) {
            unless ( $bhistory =~/$curr_b/ ) {
                main($a, $b, $lv+1, $bhistory ." ".$curr_b, $op );
            }
        } else { 
            unless ( $bhistory =~/$curr_a/ ) {
                main($b, $a, $lv+1, $bhistory ." ".$curr_a, $op );
            }
        }
    }

    if ($chk == 2) {
        my $ta = [@arr];
        my $tb = [@brr];
        for my $id ( 0 .. $#$op ) {
            if ( $id % 2 == 0 ) {
                cross_river( $ta, $tb, $op->[$id] );
                printf "[%2d]   Go %d,%d,%d ", $id+1, @{$op->[$id]};
            } else {
                cross_river( $tb, $ta, $op->[$id] );
                printf "[%2d] Back %d,%d,%d ", $id+1, @{$op->[$id]};
            }
            printf "A [%d %d %d], B [%d %d %d]\n", @$ta, @$tb;
        }
        printf "\n";
    }

    cross_river( $b, $a, [$h,$w,$s] ); # 恢复
}

sub cross_river {
    my ($a,$b,$c) = @_;
    grep { $a->[$_]-=$c->[$_],
           $b->[$_]+=$c->[$_]; } (0,1,2);
}

sub check {
    my ($a, $b, $lv) = @_;
    return 0 if ( $a->[1] >= $a->[2] and $a->[2] > 0 and $a->[0] == 0 );
    return 0 if ( $b->[1] >= $b->[2] and $b->[2] > 0 and $b->[0] == 0 );
    return 2 if ( $a->[1] == 0 and $a->[2] == 0 );
    return 1;
}
复制代码

[ 1]   Go 1,1,0 A [0 2 3], B [1 1 0]
[ 2] Back 1,0,0 A [1 2 3], B [0 1 0]
[ 3]   Go 1,2,0 A [0 0 3], B [1 3 0]
[ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
[ 5]   Go 1,0,2 A [0 0 1], B [1 3 2]
[ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
[ 7]   Go 1,0,1 A [0 2 0], B [1 1 3]
[ 8] Back 1,0,0 A [1 2 0], B [0 1 3]
[ 9]   Go 1,2,0 A [0 0 0], B [1 3 3]

[ 1]   Go 1,1,0 A [0 2 3], B [1 1 0]
[ 2] Back 1,0,0 A [1 2 3], B [0 1 0]
[ 3]   Go 1,2,0 A [0 0 3], B [1 3 0]
[ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
[ 5]   Go 1,0,2 A [0 0 1], B [1 3 2]
[ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
[ 7]   Go 1,1,1 A [0 1 0], B [1 2 3]
[ 8] Back 1,0,0 A [1 1 0], B [0 2 3]
[ 9]   Go 1,1,0 A [0 0 0], B [1 3 3]

[ 1]   Go 1,2,0 A [0 1 3], B [1 2 0]
[ 2] Back 1,0,0 A [1 1 3], B [0 2 0]
[ 3]   Go 1,1,0 A [0 0 3], B [1 3 0]
[ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
[ 5]   Go 1,0,2 A [0 0 1], B [1 3 2]
[ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
[ 7]   Go 1,0,1 A [0 2 0], B [1 1 3]
[ 8] Back 1,0,0 A [1 2 0], B [0 1 3]
[ 9]   Go 1,2,0 A [0 0 0], B [1 3 3]

[ 1]   Go 1,2,0 A [0 1 3], B [1 2 0]
[ 2] Back 1,0,0 A [1 1 3], B [0 2 0]
[ 3]   Go 1,1,0 A [0 0 3], B [1 3 0]
[ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
[ 5]   Go 1,0,2 A [0 0 1], B [1 3 2]
[ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
[ 7]   Go 1,1,1 A [0 1 0], B [1 2 3]
[ 8] Back 1,0,0 A [1 1 0], B [0 2 3]
[ 9]   Go 1,1,0 A [0 0 0], B [1 3 3]
复制代码

[ 1]   Go 1,4,0 A [0 3 7], B [1 4 0]
[ 2] Back 1,0,0 A [1 3 7], B [0 4 0]
[ 3]   Go 1,3,0 A [0 0 7], B [1 7 0]
[ 4] Back 1,0,0 A [1 0 7], B [0 7 0]
[ 5]   Go 1,0,4 A [0 0 3], B [1 7 4]
[ 6] Back 1,4,0 A [1 4 3], B [0 3 4]
[ 7]   Go 1,1,3 A [0 3 0], B [1 4 7]
[ 8] Back 1,0,0 A [1 3 0], B [0 4 7]
[ 9]   Go 1,3,0 A [0 0 0], B [1 7 7]
复制代码

    [ 1]   Go 1,9,0 A [0 8 17], B [1 9 0]
    [ 2] Back 1,0,0 A [1 8 17], B [0 9 0]
    [ 3]   Go 1,8,0 A [0 0 17], B [1 17 0]
    [ 4] Back 1,0,0 A [1 0 17], B [0 17 0]
    [ 5]   Go 1,0,9 A [0 0 8], B [1 17 9]
    [ 6] Back 1,9,0 A [1 9 8], B [0 8 9]
    [ 7]   Go 1,1,8 A [0 8 0], B [1 9 17]
    [ 8] Back 1,0,0 A [1 8 0], B [0 9 17]
    [ 9]   Go 1,8,0 A [0 0 0], B [1 17 17]
复制代码

拉8狼过，回 此时wolf=9,8
拉7狼过，回 此时wolf=2,15
拉8羊过，拉8狼回 此时wolf=10,7 sheep=9,8
船上放置2狼，每次载3狼3羊过去即可。
复制代码

[ 1]   Go 1,4,0 A [0 13 17], B [1 4 0]
[ 2] Back 1,0,0 A [1 13 17], B [0 4 0]
[ 3]   Go 1,3,0 A [0 10 17], B [1 7 0]
[ 4] Back 1,0,0 A [1 10 17], B [0 7 0]
[ 5]   Go 1,0,4 A [0 10 13], B [1 7 4]
[ 6] Back 1,4,0 A [1 14 13], B [0 3 4]
[ 7]   Go 1,3,1 A [0 11 12], B [1 6 5]
[ 8] Back 1,2,0 A [1 13 12], B [0 4 5]
[ 9]   Go 1,3,1 A [0 10 11], B [1 7 6]
[10] Back 1,2,0 A [1 12 11], B [0 5 6]
[11]   Go 1,3,1 A [0 9 10], B [1 8 7]
[12] Back 1,2,0 A [1 11 10], B [0 6 7]
[13]   Go 1,3,1 A [0 8 9], B [1 9 8]
[14] Back 1,2,0 A [1 10 9], B [0 7 8]
[15]   Go 1,3,1 A [0 7 8], B [1 10 9]
[16] Back 1,2,0 A [1 9 8], B [0 8 9]
[17]   Go 1,3,1 A [0 6 7], B [1 11 10]
[18] Back 1,2,0 A [1 8 7], B [0 9 10]
[19]   Go 1,3,1 A [0 5 6], B [1 12 11]
[20] Back 1,2,0 A [1 7 6], B [0 10 11]
[21]   Go 1,3,1 A [0 4 5], B [1 13 12]
[22] Back 1,2,0 A [1 6 5], B [0 11 12]
[23]   Go 1,3,1 A [0 3 4], B [1 14 13]
[24] Back 1,2,0 A [1 5 4], B [0 12 13]
[25]   Go 1,3,1 A [0 2 3], B [1 15 14]
[26] Back 1,2,0 A [1 4 3], B [0 13 14]
[27]   Go 1,1,3 A [0 3 0], B [1 14 17]
[28] Back 1,0,0 A [1 3 0], B [0 14 17]
[29]   Go 1,3,0 A [0 0 0], B [1 17 17]
复制代码

载4狼过，回
载3狼过，回
载4羊过，载4狼回
船上装2狼，每次运送1狼1羊
复制代码

载2狼1羊过，载2狼回
船上装2狼，每次运送1狼1羊
复制代码