7人1狼过河问题

lihpb00

剑客A和剑客B各带着 2 个仆人，猎人带了 1 条狼过河。河上有条船，每次只能运 2 个人或者1人1 狼，只有猎人和两个剑客会撑船。

当剑客A不在的时候，剑客B会杀掉剑客A的两个仆人，
当剑客B不在的时候，剑客A会杀掉剑客B的两个仆人，
当没有其他人在的时候，剑客A和B会决一死战同归于尽。
当没有猎人在的时候，狼会与人发生冲突。

要求把7人一狼平安送过河

曹半

一笔画问题

mathe

1狼和猎人过河，猎人回
2猎人和A仆人1过河，A仆人1回
3.A仆人1+2过河，A仆人1回
4.A+A仆人1过河，猎人+狼回
5.B+B仆人1过河，B仆人1回
6.B仆人1+2过河，B仆人1回
7.B仆人1+猎人过河，猎人回
8.猎人加狼过河

mathe

只有猎人和剑客能够开船应该不行了，计算机穷举了一下

$ ./moving
Total 136 valid states
Not reachable
Final best state:{ DogA1 DogA2 Hunter Wolf Boat }{ KnightA KnightB DogB1 DogB2 }
Left to Right: { Hunter Wolf Boat }:state:{ DogA1 DogA2 }{ KnightA KnightB DogB1 DogB2 Hunter Wolf Boat }
Right to Left: { KnightA Boat }:state:{ KnightA DogA1 DogA2 Boat }{ KnightB DogB1 DogB2 Hunter Wolf }
Left to Right: { KnightA DogA2 Boat }:state:{ DogA1 }{ KnightA DogA2 KnightB DogB1 DogB2 Hunter Wolf Boat }
Right to Left: { Hunter Wolf Boat }:state:{ DogA1 Hunter Wolf Boat }{ KnightA DogA2 KnightB DogB1 DogB2 }
Left to Right: { DogA1 Hunter Boat }:state:{ Wolf }{ KnightA DogA1 DogA2 KnightB DogB1 DogB2 Hunter Boat }
Right to Left: { Hunter Boat }:state:{ Hunter Wolf Boat }{ KnightA DogA1 DogA2 KnightB DogB1 DogB2 }
Left to Right: { Hunter Wolf Boat }:state:{ }{ KnightA DogA1 DogA2 KnightB DogB1 DogB2 Hunter Wolf Boat }

mathe

只要把一只狗替换成仆人（能够开船），就可以了
$ ./moving2
Total 136 valid states
Left to Right: { Hunter Wolf Boat }:state:{ KnightA ServantA1 DogA2 KnightB DogB1 DogB2 }{ Hunter Wolf Boat }
Right to Left: { Hunter Boat }:state:{ KnightA ServantA1 DogA2 KnightB DogB1 DogB2 Hunter Boat }{ Wolf }
Left to Right: { ServantA1 Hunter Boat }:state:{ KnightA DogA2 KnightB DogB1 DogB2 }{ ServantA1 Hunter Wolf Boat }
Right to Left: { ServantA1 Boat }:state:{ KnightA ServantA1 DogA2 KnightB DogB1 DogB2 Boat }{ Hunter Wolf }
Left to Right: { ServantA1 DogB2 Boat }:state:{ KnightA DogA2 KnightB DogB1 }{ ServantA1 DogB2 Hunter Wolf Boat }
Right to Left: { ServantA1 Boat }:state:{ KnightA ServantA1 DogA2 KnightB DogB1 Boat }{ DogB2 Hunter Wolf }
Left to Right: { KnightB DogB1 Boat }:state:{ KnightA ServantA1 DogA2 }{ KnightB DogB1 DogB2 Hunter Wolf Boat }
Right to Left: { Hunter Wolf Boat }:state:{ KnightA ServantA1 DogA2 Hunter Wolf Boat }{ KnightB DogB1 DogB2 }
Left to Right: { KnightA ServantA1 Boat }:state:{ DogA2 Hunter Wolf }{ KnightA ServantA1 KnightB DogB1 DogB2 Boat }
Right to Left: { ServantA1 Boat }:state:{ ServantA1 DogA2 Hunter Wolf Boat }{ KnightA KnightB DogB1 DogB2 }
Left to Right: { Hunter Wolf Boat }:state:{ ServantA1 DogA2 }{ KnightA KnightB DogB1 DogB2 Hunter Wolf Boat }
Right to Left: { KnightA Boat }:state:{ KnightA ServantA1 DogA2 Boat }{ KnightB DogB1 DogB2 Hunter Wolf }
Left to Right: { KnightA ServantA1 Boat }:state:{ DogA2 }{ KnightA ServantA1 KnightB DogB1 DogB2 Hunter Wolf Boat }
Right to Left: { ServantA1 Boat }:state:{ ServantA1 DogA2 Boat }{ KnightA KnightB DogB1 DogB2 Hunter Wolf }
Left to Right: { ServantA1 DogA2 Boat }:state:{ }{ KnightA ServantA1 DogA2 KnightB DogB1 DogB2 Hunter Wolf Boat }

mathe

更好的方案是每个剑客带着一个仆人一条狗，但是高高在上的剑客不会划船

$ ./moving3
Total 136 valid states
Left to Right: { Hunter Wolf Boat }:state:{ KnightA ServantA DogA KnightB ServantB DogB }{ Hunter Wolf Boat }
Right to Left: { Hunter Boat }:state:{ KnightA ServantA DogA KnightB ServantB DogB Hunter Boat }{ Wolf }
Left to Right: { ServantB Hunter Boat }:state:{ KnightA ServantA DogA KnightB DogB }{ ServantB Hunter Wolf Boat }
Right to Left: { ServantB Boat }:state:{ KnightA ServantA DogA KnightB ServantB DogB Boat }{ Hunter Wolf }
Left to Right: { ServantB DogB Boat }:state:{ KnightA ServantA DogA KnightB }{ ServantB DogB Hunter Wolf Boat }
Right to Left: { ServantB Boat }:state:{ KnightA ServantA DogA KnightB ServantB Boat }{ DogB Hunter Wolf }
Left to Right: { KnightB ServantB Boat }:state:{ KnightA ServantA DogA }{ KnightB ServantB DogB Hunter Wolf Boat }
Right to Left: { Hunter Wolf Boat }:state:{ KnightA ServantA DogA Hunter Wolf Boat }{ KnightB ServantB DogB }
Left to Right: { KnightA ServantA Boat }:state:{ DogA Hunter Wolf }{ KnightA ServantA KnightB ServantB DogB Boat }
Right to Left: { ServantA Boat }:state:{ ServantA DogA Hunter Wolf Boat }{ KnightA KnightB ServantB DogB }
Left to Right: { Hunter Wolf Boat }:state:{ ServantA DogA }{ KnightA KnightB ServantB DogB Hunter Wolf Boat }
Right to Left: { ServantB Boat }:state:{ ServantA DogA ServantB Boat }{ KnightA KnightB DogB Hunter Wolf }
Left to Right: { DogA ServantB Boat }:state:{ ServantA }{ KnightA DogA KnightB ServantB DogB Hunter Wolf Boat }
Right to Left: { ServantB Boat }:state:{ ServantA ServantB Boat }{ KnightA DogA KnightB DogB Hunter Wolf }
Left to Right: { ServantA ServantB Boat }:state:{ }{ KnightA ServantA DogA KnightB ServantB DogB Hunter Wolf Boat }

lihpb00

mathe 发表于 2024-8-17 07:52
只有猎人和剑客能够开船应该不行了，计算机穷举了一下

$ ./moving

当没有其他人在的时候，剑客A和B会决一死战同归于尽。这个条件是错的


不好意思，条件里面有一个写错了
当没有其他人在的时候，剑客A的仆人们和B的仆人们会决一死战同归于尽。