java - 具有递归回溯的动态树构建

Question

我有这个问题，我需要解决递归回溯问题。它看起来很像 n 皇后问题，但不同之处在于它使用具有非对称棋盘的不同候选人。总共有四个不同的候选人，每个候选人都依赖于一个和另一个。我有 2 个 A、2 个 K、2 个 Q 和 2 个 J。每个 A 必须紧挨着(水平或垂直)一个国王，每个国王必须紧挨着一个女王，每个女王必须紧挨着一个千斤顶，并且没有一件可以在他们旁边重复。具有正确解决方案的电路板如下所示:

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 .

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

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

Answer 1

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

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