algorithm - Frog 和蟾蜍

Question

我是 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]

Answer 1

我通过以下方式知道了这个谜语。但我猜跳蛙/蟾蜍比跳 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 列表。