我有一个拼图游戏，它的State取决于拼图中各个部分的排列。我试图使用深度优先搜索来解决这个拼图，但我对如何着手感到困惑。据我所知，深度优先搜索会搜索图形以找到解决方案，但我的拼图并不是图形形式。我只知道当前状态以及从该状态可达的状态。

我是否应该在发现当前状态的所有可能状态时构建这个图形？但这样做不是违背了初衷吗——首先构建包含所有可能状态的图形，然后搜索整个图形以寻找解决方案？

我有一个方法，可以使用Move探索从当前状态的所有可能状态，我确信这会派上用场，只是我不知道如何使用它。

回答：

你不需要明确地构建一个图形。你可以概念上将你的问题表示为一个图形，其中节点是状态，边是状态之间的转换。深度优先搜索是沿着一个边一直走，直到你到达一个终止状态，然后再移动到另一个边。所以它看起来会像这样（伪代码）：

def search(state):    if is_end_state(state):        # 搜索这一分支完成，执行某些操作        return something    for move in possible_moves_from(state):        search(apply_move(state, move))

你最终会通过递归调用和堆栈状态隐式地构建图形，在你进行的过程中。

请注意，如果你有循环（例如，你可以向左移动，然后向右移动回到完全相同的状态），那么你必须跟踪已经访问过的状态，否则你会永远循环。像这样：

def search(state, seen_states):    if state in seen_states:        # 已经访问过，不再访问        return     seen_states.add(state)    # 与之前相同：          if is_end_state(state):        return something    for move in possible_moves_from(state):        search(apply_move(state, move), seen_states)

关于如何实现这一点，我建议你将seen_states设为HashSet<State>，并使你的State可哈希。