小编Mat*_*ssy的帖子

于是我阿姨就玩这款现在很流行的手机游戏，如下图所示。她卡在某个关卡上，问我是否可以解决。知道我不够聪明，无法找到解决问题的模式或策略，并且只了解 Python 的基础知识，我认为我应该尝试通过编写脚本来解决它，这是学习新东西的绝佳机会，我开始了为期两周的旅程。

游戏由多个瓶子组成，里面装满了层层不同颜色的瓶子，一般还有一到两个空瓶子，目标是让所有瓶子颜色统一。一个动作包括将一个瓶子至少装满一层并将其倒入另一个瓶子中。主要规则是您可以在空瓶子中倒入任何颜色，并且只有在颜色相同的情况下才可以将一层倒入另一层上。

我解决这个问题的第一个方法是创建一个新的class bottle，实现其中的所有规则，这意味着因为我只知道基础知识，所以花了我很多时间而且它确实没有优化（我不了解堆栈）并且必须写下这么多if.. elif.. else语句来指定一个瓶子何时可以倒入另一个瓶子中）。完成后，我尝试编写一些可以解决该问题的代码。对于代码如何知道选择哪个瓶子以及将其倒到哪里，我没有太多想法，所以我采用了简单的解决方案：随机选择它们。对于少量瓶子，它立即（有点）解决了这个问题，我上次尝试的是 10 瓶，但对于 15 瓶或更多，它不能。

所以我的第二个想法是计算每一个可能性和移动，即制作游戏树，然后使用搜索算法来找到最短路径，我读了一些关于游戏树和图的搜索算法并决定使用广度 -第一次搜索（后来我了解到我使用的图是有向无环图，所以最好使用拓扑排序，我不确定）。游戏树中的节点是瓶子相互倒入后所处的不同状态，边缘是从一种状态到另一种状态的移动。以下是我如何用伪代码生成游戏树：

take the first bottle A
create a list of bottles, list A, that bottle A can pour in
for each bottle B in list A, we pour bottle A in bottle B, and get a new state of bottles C
check if state C is already a node in the graph, or a permutation of a node(see explanation after the code) and …