prolog - Prolog：解决 Peg Jumping 问题（启发式/A*）

Question

我正在尝试解决以下问题：

一个拼图由三个黑色钉子、三个白色钉子和中间的空白区域（“BBBOWWW”）组成。

这个谜题有两个带有相关成本的移动： (a) 一个钉子可能会移动到一个相邻的空位置（成本为 1）。(b) 一个钉子可以跳过一两个其他钉子进入空位。其成本等于跳过的钉子数量。

目标是将所有白色钉子放在所有黑色钉子的左侧。空白的位置并不重要。

我可以使用我选择的任何编程语言，并希望使用 Prolog 来解决这个问题以获得经验。我已经能够实现这个问题的简化版本，它可以找到最短路径，但在 A* 和启发式实现方面遇到了困难。

我附上了以下 Prolog 代码和我正在使用的查询。

我的问题是如何在我的代码中实现 A* 算法？我无法找到有用的示例，并希望得到任何指导/提示。

谢谢你。

询问：

length(Path, _),
initial_state(Initial),
phrase(moves(Initial), Path),
maplist(writeln, Path).

程序：

% Initial state
initial_state([b,b,b,o,w,w,w]).

% 7 possible goal states
goalState([w,w,w,o,b,b,b]).
goalState([w,w,w,b,o,b,b]).
goalState([w,w,w,b,b,b,o]).
goalState([w,w,o,w,b,b,b]).
goalState([w,o,w,w,b,b,b]).
goalState([o,w,w,w,b,b,b]).

% All possible moves
move([E|Es]) --> [E], move(Es).
move([b,o|Solution]) --> [o,b], list(Solution). 
move([o,w|Solution]) --> [w,o], list(Solution).
move([o,X,w|Solution]) --> [w,X,o], list(Solution).
move([b,X,o|Solution]) --> [o,X,b], list(Solution).
move([o,X,X,w|Solution]) --> [w,X,X,o], list(Solution).
move([b,X,X,o|Solution]) --> [o,X,X,b], list(Solution).
move([w,X,X,o|Solution]) --> [o,X,X,w], list(Solution).
move([o,X,X,b|Solution]) --> [b,X,X,o], list(Solution).

list([]) --> [].
list([L|Solution]) --> [L], list(Solution).

moves(S)  --> [S], {goalState(S)}.
moves(S0) --> [S0], {phrase(move(S0),S)}, moves(S).

我的初始解决方案基于以下内容： Prolog program that solve the peg jump puzzle

标签： prologshortest-patha-star