我是 Prolog 的新手,遇到了一个看起来很容易实现的逻辑谜题,但在网上搜索了 2 天后,我仍然无法理解如何在 Prolog 中解决它。
三只 Frog 和三只蟾蜍排成一排,如下图的起始状态所示。 Frog 在右边,蟾蜍在左边。通过一系列有效的两栖移动,您必须将状态转换为目标状态,如下图所示。
但是 Frog 和蟾蜍只能按照以下规范移动:
- 一次只能有一种两栖动物(即 Frog 或蟾蜍)移动。
- Frog 只能向左移动,蟾蜍只能向右移动。
- 每一步都是爬行或跳跃。
- 爬行是移动到相邻的空白空间。
- 跳跃是移动到距离起始空间两个空间的空白空间,这样跳跃的起点和终点之间的空间被另一只两栖动物占据。
- Frog 只能跳过蟾蜍,而蟾蜍只能跳过 Frog 。
编辑
我想实现的是 Frog 和蟾蜍可以做出的所有可能的 Action ,手动,我已经解决了这个问题,但我想实现它,以便程序在执行最少的 Action 的同时解决它。
这是我正在尝试做的事情:
初始状态:[frog1,frog2,frog3,gap,toad3,toad2,toad1]
transition_1: [frog1,frog2,gap,frog3,toad3,toad2,toad1] transition_2: [frog1,frog2,toad3,frog3,gap,toad2,toad1]
.
.
.
最终状态::[toad3,toad2,toad1,gap,frog1,frog2,frog3]
最佳答案
我通过以下方式知道了这个谜语。但我猜跳蛙/蟾蜍比跳 Camel 更合理:
Two caravans of camels cross in a narrow valley.
这是一个简单的解决方案,使用蛮力和 Camel 习语,前者是因为搜索空间没有循环并且是有限的:
/* right facing camel advances */
move([0'>, 0' |L], [0' , 0'>|L]).
/* left facing camel advances */
move([0' , 0'<|L], [0'<, 0' |L]).
/* right facing camel jumps */
move([0'>, 0'<, 0' |L], [0' , 0'<, 0'>|L]).
/* left facing camel jumps */
move([0' , 0'>, 0'<|L], [0'<, 0'>, 0' |L]).
/* search move further right */
move([X|L], [X|R]) :- move(L, R).
find(X, X).
find(X, Y) :- move(X, H), find(H, Y).
好像有两种解决办法:
?- find(">>> <<<", "<<< >>>").
Yes ;
Yes ;
No
作业:修改上面的代码,让它显示一个 Action 列表。
关于algorithm - Frog 和蟾蜍,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53693326/