解谜器 - TreeNode 帮助
我正在尝试编写一个解谜应用程序。 我需要找出需要多少步，以及有多少种解决方案。
我不想透露太多关于这个谜题的细节。 但玩家绕着网格移动（比如 5 x 7 ） 当它们移动时，可以捕获障碍物，因此需要跟踪板的状态。 （这可以作为字符串或数组来完成）
我知道我需要创建一个 TreeNode，从根开始（玩家的起始位置） 并为每个节点提供可能的移动的子节点，直到计算出所有可能的移动。 然后可以收集谜题统计数据。 可能的解决方案数、要解决的最小移动数、要解决的平均移动数等。
我创建了谜题逻辑，如果移动可能等，该逻辑将返回。 我在创建 TreeNode 结构并确保移动不重复时遇到问题。
拼图应用程序本身位于 iPhone 上，但我正在 Mac 上编写这个解算器/编辑器。 任何帮助将非常感激。
I'm trying to code a puzzle solver app.
I need to find out how many moves it takes, and how many solutions there are.
I would rather not give too many details on the puzzle.
but the player moves around a grid ( say 5 x 7 )
as they move, obstacles could be captured so the state of the board needs to be tracked.
( this could be done as a string or an array )
I understand I need to create a TreeNode, starting with a root ( the players start position )
and give each node children of the possible moves until all the possible moves are calculated.
The puzzle stats could then be collected.
Number of Possible solutions, minimum number of moves to solve, average number of moves to solve, etc.
I have the puzzle logic created that will return if moves are possible and such.
I'm having problems creating the TreeNode structure and making sure moves are not duplicated.
The puzzle app itself is on the iPhone, but I'm writing this solver/editor on the Mac.
Any help would be VERY much appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
也许你可以做一个树递归的变体？递归地遍历树，让每个末端节点返回一个值，表示到达那里的难度（如果存在与不同移动相关的成本）以及如何到达那里的描述。这当然要求玩家只能朝一个方向移动，否则树结构无法描述问题。有关您的具体问题的更多信息将会有所帮助。
这可能是一个繁重的算法，但它可以完成工作。
Perhaps you could do a variant of a tree recursion? Traverse the tree recursively, having each end node return a value of how hard it was to get there (if there are costs associated with different moves) and a description of how it got there. This of course requires the player to only move in one direction, otherwise the tree-structure doesn't describe the problem. A bit more info on what your exact problem looks like would be helpful.
It might be a heavy algorithm, but it gets the job done.
为了检测重复的状态，您可以将状态放入一个集合中，然后每次发现新状态时检查它们是否已经存在。不过，如果空间是一个问题，您将不得不仅检查子级是否与父级相同，或者这种方法的某种有限版本。
节点类非常简单。它只包含一个返回父级的指针（如果有的话）和它保存的变量（例如状态）。根据您的应用程序，您可能还需要其他变量。
当到达一个节点时，您可以使用后继函数从那里获取所有子节点（一次移动即可到达的状态）并将它们添加到列表中。您从列表中选取内容来遍历树。
For detecting repeated states, you would put the states in a set as you went along, and then check every time you found new states to see if they already existed. Though if space is an issue, you will have to resort to only checking if the children are not the same as the parent, or some kind of limited version of this approach.
A node class is very simple. It just contains a pointer back to a parent (if it has one) and the variable it holds (such as a state). You will also probably want other variables depending on your application.
When you get to a node, you use a successor function to get all the child nodes from there (the states that can be reached in one move) and add them to a list. You pluck from the list to traverse the tree.