3

我有这个问题，我需要解决递归回溯问题。它看起来很像 n-queen 问题，但不同之处在于它使用具有非对称板的不同候选人。总共有四个不同的候选人，每个候选人都相互依赖。我有 2 个 A、2 个 K、2 个 Q 和 2 个 J。每个王牌必须靠近（水平或垂直）国王，每个国王必须靠近皇后，每个皇后必须靠近杰克，并且任何棋子旁边都不能有重复。具有正确解决方案的电路板如下所示：

Grid (y, x)(only the positions between *y,x* are available for candidates): 
4,1 4,2 *4,3* 4,4
3,1 *3,2* *3,3* *3,4*
*2,1* *2,2* *2,3* 2,4
1,1 1,2 *1,3* 1,4

Possible Solution
. . K . 
Q J Q .
. A K A
. . J .

现在我的问题是我想使用一棵树来跟踪作为树的父母和孩子的候选人。我还没有实现树，但我想知道这个例子中显示的方法是否是创建树的好方法。如果这是创建树的好方法，我该如何开始，树如何知道它应该在孩子身上找到哪个父母，并在解决方案不适合时返回？

我希望我已经添加了有关这种情况的足够信息，在此先感谢。

4

1 回答 1

1

我在这里可能错了，但看起来你并没有完全掌握递归搜索算法在这种情况下应该如何工作。您要构建的树结构通常不会显式实现，而是看起来像搜索树的递归调用结构。如果您查看此处的伪代码实现http://en.wikipedia.org/wiki/Backtracking，您将看到没有涉及树结构，并且回溯（在拒绝返回 true 时完成）仅通过返回来完成从当前调用开始。

在您的情况下，您可能希望在单个数据结构上进行搜索，而不是复制它，因此回溯意味着删除您刚刚放下的候选部分，然后返回。

于 2011-02-12T15:58:44.063 回答