这些都是递归解

Question

每个人都知道饼干桶三角桩接龙游戏。你拿一个钉子，跳过另一个，跳进一个空洞，目标是只剩下一个钉子。

在游戏板对象的代码中，我有一个函数sCpeg（inta，intb），它改变了你当前用来跳转的peg。为了解决这个问题，我将其连接到一个moves变量。每次你改变当前的钉住并使用它跳跃时，这算是一次移动。这是一个非常基本的启发式搜索算法，我希望是一个搜索算法：探索所有可能的跳跃可用一个peg。如果没有找到回溯的解决方案，请更新当前的peg并重复该过程。

当我写下这个想法时，这听起来像是一个使用递归的完美例子，只是我不知道如何在这个场景中正确使用递归。在回溯和更新当前peg之间，我迷失了方向。

这一切听起来太复杂了吗？我是否应该删除移动和sCpeg（）选项，让搜索算法随机跳转，直到找到解决方案？

递归是解决这个难题的好方法吗？我的跳转函数目前只要求你想跳到的位置。我必须改变它，以获得每次跳转所需的开始和结束位置，这很容易改变，但我不知道对算法来说是好是坏。

这是一个学校项目，所以我必须实现一个不知情的搜索和一个启发式搜索算法。改变我的<代码>跳转（）函数可能会影响我的启发式。

我用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

我想就这些了。

这类问题还有另一个框架：图形理论。图的节点是板状态。如果你能从另一个得到一个，我们用箭头连接两个板状态。然后你在图中搜索连接开始到结束的最短路径...使用有向图算法中的任何标准最短路径。

但是你的递归想法应该很好用。