具有递归回溯的动态树构建
我有这个问题，我需要解决递归回溯问题。它看起来很像 n 皇后问题，但不同之处在于它在非对称董事会上使用不同的候选者。总共有四个不同的候选者，每个候选者都相互依赖。我有 2 个 A、2 个 K、2 个 Q 和 2 个 J。每个 A 必须紧邻（水平或垂直）一个 K，每个 K 必须紧邻一个 Queen，每个 Queen 必须紧邻一个 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 .
现在我的问题是我想使用一棵树来跟踪候选人作为树的父母和孩子。我尚未实现该树，但我想知道此示例中所示的方法是否是创建树的好方法。如果这是创建树的好方法，那么我该如何开始，树如何知道它应该在子节点上指向哪个父节点，并且在解决方案不适合时返回？
我希望我已经添加了有关这种情况的足够信息，提前致谢。
I have this problem that I need to solve a recursive backtracking issue. It looks a lot like the n-queen problem, but is different in the way that it uses different candidates with a a-symmetric board. There are a total of four different candidates that each have dependency's on one and another. I have 2 aces, 2 kings, 2 queens and 2 jacks. Each ace has to be next to (horizontal or vertical) to a king, each king has to be next to a queen and each queen has to be next to a jack and non of the pieces can have duplicates next to them. The board with the right solution looks like this:
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 .
Now my problem is that I want to use a tree to keep track of the candidates as parents and children of a tree. I have not yet implemented the tree, but I was wondering if the method as shown in this example is a good way to create a tree from. And if this is a good way to create a tree from, how do I start, how does the tree know to which parent it should at a child and also go back when the solution doesn't fit?
I hope I've added enough information about this situation, thanks in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我在这里可能是错的，但看起来您并没有完全掌握递归搜索算法在这种情况下应该如何工作。您想要构建的树结构通常不会显式实现，而是看起来像搜索树的递归调用结构。如果您查看此处的伪代码实现 http://en.wikipedia.org/wiki/Backtracking ，您将看到不涉及树结构，并且回溯（当reject返回true时完成）只是通过从当前调用返回来完成。
在您的情况下，您可能希望对单个数据结构进行搜索，而不是复制它，因此回溯意味着删除您刚刚放下的候选块，然后返回。
I may be wrong here, but it doesn´t look like you´ve completely grasped how the recursive search algorithm should work in this case . The tree structure you want to build is typically not explicitly implemented, instead it is the structure of recursive calls that will look like a search tree. If you look at the pseudo-code implementation here http://en.wikipedia.org/wiki/Backtracking , you will see that there is no tree structure involved, and the backtracking (done when reject returns true) is done just by returning from the current invocation.
In your case you may want to do the search on a single data structure, instead of copying it, so backtracking means removing the candidate piece you just put down, and then returning.