Peg solitare递归解

Question

每个人都知道饼干桶三角形钉纸牌游戏。您取一个钉子，然后将其跳过另一个钉子进入一个空洞，目标是只剩下一个钉子。

在游戏板对象的代码中，我具有函数sCpeg(int a, int b)，该函数可更改您当前用于跳跃的桩钉。我将其连接到moves变量以解决它。每次您更改当前钉子并使用它来跳跃时，这都算是一个动作。对于我希望成为搜索算法的事情，它是一种非常基本的启发式方法：探索使用一个钉子进行的所有可能的跳跃。如果找不到回溯的解决方案，请更新当前钉并重复该过程。

[当我写出这个想法时，听起来像是一个使用递归的完美例子，除了我不知道如何在这种情况下正确使用递归。在回溯和更新当前钉之间，我迷路了。

所有这些听起来是否太复杂？我是否应该只删除moves和sCpeg()选项，并让搜索算法随机跳转直到找到解决方案？

递归是解决这个难题的好方法吗？我的跳转功能当前仅通过询问您想跳转到的位置来工作。我必须将其更改为每次跳转所需的开始和结束位置，更改很容易，但是我不知道它对算法的好坏。

这是针对学校项目的，因此我必须实施不知情的搜索和启发式搜索算法。更改jump()函数可能会影响我的启发式。

我正在用Java进行编码，但是由于这有点含糊，我只希望得到伪代码答案。仅伪代码就足以使我走上正轨。 。

Answer 1

这是递归解决方案的框架：

// given a board description, outputs solution sequence string, or null if no soln
public String sCpeg(boardDescription bd)
  if bd is solution state, return "" // termination of successful recursion
  for each possible move m
    calculate result of m on bd to obtain newbd
    store result of sCpeg(newbd) in subresult
    if subresult is not null, return m + subresult
  end for
  // if we're here, no move worked -- termination, unsuccessful
  return null

我认为这就是全部。

还有另一种解决这类问题的框架：图论。图的节点是板状态。如果您可以从另一个板状态中获得另一个，则可以用箭头将它们连接起来。然后，您在连接起点到终点的图形中搜索最短路径...使用二字算法中的任何标准最短路径。

但是您的递归想法应该可以正常工作。