我制作了一个拼图游戏，玩家需要滑动方块到目标位置 – 规则相当简单：
- 每次只能移动一个滑动方块
- 目标是将滑动方块移动到目标节点 – 你只需要填满目标节点，不一定需要所有滑动方块都进入目标节点。
- 如果滑动方块在冰面上滑动，它会继续朝那个方向移动，直到被停止或移动
- 如果滑动方块撞到固体物体（混凝土、另一个方块），它会停止并可以再次移动（显然不能移动到混凝土上）
- 如果滑动方块滑到木头上，它会在木头上停止并可以移动
- 如果滑动方块滑到目标节点，它将无法再移动
- 方块可以通过某些方块移动，例如，箭头方块会将方块朝那个方向推动
- 有开关方块可以开启“门”，这些“门”可以被移动以开启和关闭
- 有按钮方块，其操作类似于开关，但必须有方块压在上面才能激活“门”
- 当门关闭时，它们就像混凝土一样。当门打开时，它们就像冰面一样。
我想这些就是规则了。以下是一些截图：
在这里，玩家必须移动方块，使它们相互碰撞以解决拼图。
拼图接近解决的状态。注意方块如何撞到另一个方块并停止
这里是另一个包含推动方块机制的拼图：
如果我们将右上角的方块向下滑动，会发生以下情况：
如你所见，方块在撞到箭头方块后被推向左侧，并在木方块上停止。
我想编写一个AI解决方案来解决这些拼图 – 我在考虑使用某种深度优先搜索，但我不知道从哪里开始。任何关于如何实现这一点的建议都将非常有帮助！
回答：
你的问题是一个经典的状态空间搜索问题。根据你特定实例的特性，可以使用不同的算法来解决。
无论你的特定实例如何，你需要定义四个组件：
- 初始状态，在你的问题中是初始配置
- 一个函数，返回从任何状态可达的所有可能状态，在你的问题中，可达状态是通过移动滑动方块可以得到的所有可能的拼图配置。当一个状态的可达状态被访问时，该状态被称为已扩展。
- 目标测试，一个函数，判断给定状态是否为目标状态，在你的问题中，你会检查所有目标方块是否已被填满，
- 成本函数，给出从一个状态到另一个状态的成本，使你的算法能够选择执行的最佳动作。在你的情况下，我认为你可以为每个动作使用常数值1，并搜索执行的最小动作数以达到目标状态之一。
由于你的问题可以用这四个组件来定义，你的问题可以用以下算法之一来解决：
- 广度优先搜索（BFS）：我们首先测试初始状态是否为目标状态（显然对于非平凡问题不是），然后我们扩展初始状态，测试其每个可达状态，如果不是，则扩展这些状态，依此类推，按层级进行…可以使用队列来实现。
- 深度优先搜索（DFS）：从初始状态开始，测试目标，然后扩展一个邻居状态，测试目标，然后扩展该状态，依此类推，向下深入到状态空间的最深处。这可以用堆栈来实现。
为了评估哪种算法最合适，我们可以考虑以下因素：
- 完整性：算法是否保证在存在解决方案时找到解决方案？
- 最优性：算法能否找到最优解？
- 时间复杂度：需要多长时间？
- 空间复杂度：需要多少内存？
如果我们考虑BFS策略，我们可以看到它是完整的，因为它系统地按层级探索状态空间，它只有在状态深度增加时成本函数不减少的情况下才是最优的（这是我们的情况，因为所有动作都有恒定成本）。现在是坏消息：假设每个节点的扩展最多可以产生
个状态，并且第一个解决方案在深度
，那么你将需要存储和扩展最多
个状态。
在DFS的情况下，我们必须考虑到它可能会在一条路径上长时间（可能无限）卡住，而不同的选择可能很快找到解决方案。因此，当状态空间是无限时，这个算法既不完整也不最优。如果我们考虑
作为状态空间的最大深度，我们将得到最多
的空间复杂度，而时间复杂度仍然是指数级的：
。
那么，我们能做什么呢？我们可以混合这两种策略，使用迭代加深深度优先搜索。在这种搜索中，我们将从0开始迭代地运行DFS，限制最大深度到一个最大深度级别。这种方法具有两种搜索策略的优点：
空间复杂度，其中是第一个最优解的深度，时间
（我们无法做得更好），它是完整的（它会找到解决方案，因为它按层级迭代地探索所有状态），并且它是最优的（假设成本函数随路径长度非递减）出于与BFS相同的原因是最优的。
参考：人工智能：现代方法
注意：显然存在其他无信息策略，但正如书中所述，IDDFS是无信息搜索问题的一个好选择，在这种情况下你对搜索空间没有额外信息。请参阅书籍以了解其他类型的搜索策略，例如有信息搜索，我们对目标状态与当前状态的距离有一定的了解。
