动态树建筑与递归回溯

Question

我有这个问题，我需要解决递归回溯问题。它看起来很像n皇后问题，但它与使用不对称板的不同候选者的方式不同。总共有四个不同的候选人，每个候选人都有依赖关系。我有2个ace，2个国王，2个女王和2个杰克。每个王牌必须与国王相邻（水平或垂直），每个国王必须位于王后旁边，而每位王后必须位于插孔旁边，而非王牌位置必须在他们旁边有重复。恰当的解决方案的主板看起来是这样的：

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 . 

现在我的问题是，我想用一棵树来跟踪考生家长和树的孩子。我还没有实现这个树，但是我想知道这个例子中显示的方法是否是创建树的好方法。如果这是创建树的好方法，我该如何开始，树如何知道它应该在孩子身上哪个父母，并且在解决方案不适合时又回去？

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

Answer 1

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

在你的情况下，你可能想要在单个数据结构上进行搜索，而不是复制它，所以回溯意味着删除刚刚放下的候选件，然后返回。