我如何知道这个特定的难题是否仍然可以解决？

前一段时间，我做了一个简单的游戏，包括交换鸟类，把它们合并起来，创造点。这个想法是，最终，鸟会卡住，你的游戏结束，但我觉得很难想办法来检测游戏结束，所以我发表了它，没有这样的algorithm，只是希望人们会看到它为自己。不过，我仍然对解决scheme很感兴趣，希望有人能帮助我。

游戏的作品如下：

6种不同种类的鸟类分布在nxn （通常是4 x 4 ）的网格上。
对于每两只相同types的鸟，如果它们一起形成一个完美的矩形，它们就会合并成一个同types的大鸟。这意味着您可以拥有例如4 x 1或3 x 2鸟类。
足够大的鸟可以从网格中移除，生成点。 “足够大”取决于鸟类的types，有些只需要覆盖网格上的1平方，其他的2或3 。
网格上的空方块将被从上方落下的新随机鸟填满。当然，只要别的鸟不挡路。所有鸟儿都可以随时倒下，因此鸟儿向上移动是不可能的（尽管允许向上移动）。
如果两只鸟在垂直交换时具有相同的宽度，或者在水平交换时具有相同的高度，但只有当它们完全alignment时，两只鸟才能交换位置。一只鸟总是可以移动到一个空的地方，因为它的新位置将足以容纳它，而新的地方不会否定引力。
最终，2只高大/宽阔的鸟类将阻止进一步的进步。有些鸟仍然可以交换，也许有些鸟甚至可以变得足够大，与其他一些鸟结合在一起，但是它们永远不会彼此接近，导致游戏结束。

游戏结束的一个例子。

我不太清楚这是否足够清楚。我真的不想在这里发布一个游戏的链接，因为我真的只对algorithm感兴趣，而不是新的下载。我也不太清楚，如果我被允许，因为它可以被看作是一个广告。但是请在需要的地方请求更清晰！

我觉得从蛮力解决scheme开始就不错，因为search空间相对较小。

在每一回合开始时，recursion地看看所有可以做出的动作，存储已经看过的布局，以避免重复自己。如果你能在合理的时间内find一系列导致鸟类合并的动作，拼图还没有被卡住。

例如，给出这个例子的网格：

 +-+---+ |A| B | +-+---+ |B|A|B| +-+-+-+

我们可以换上第一排的鸟：

  vv +-+---+ +---+-+ |A| B | | B |A| +-+---+ --> +-+-+-+ |B|A|B| |B|A|B| +-+-+-+ +-+-+-+

接下来，我们不交换最上面的一行，因为这会重复第一个网格。相反，我们可以交换最后一列：

  vv +-+---+ +---+-+ +---+-+ |A| B | | B |A| | B |B|< +-+---+ --> +-+-+-+ --> +-+-+-+ |B|A|B| |B|A|B| |B|A|A|< +-+-+-+ +-+-+-+ +-+-+-+

…导致可以合并的鸟对：

  vvv +-+---+ +---+-+ +---+-+ +-----+ |A| B | | B |A| | B |B|< | B | +-+---+ --> +-+-+-+ --> +-+-+-+ --> +-+---+ |B|A|B| |B|A|B| |B|A|A|< |B| A | +-+-+-+ +-+-+-+ +-+-+-+ +-+---+ ^

我们完成了。

如果我们已经用尽search空间而没有find可以合并的对，游戏就会停滞不前。也有可能我们不能在合理的时间内find结果，但考虑到有限的鸟类types（6）和网格尺寸（4×4和更大），这是不太可能的。你可以增加一个启发式的方法来改善你的search策略，如果search速度太慢的话，可以使相似types的鸟类靠得更近。

这不是一个完美的解决scheme，因为尽管可以合并，游戏最终还是会被卡住。我不认为你会需要这样一个好的求职者。大多数的益智游戏都会使用这个简单的不可移动的现在简单的求解器。