麻将-纸牌算法，它需要加速。

Question

我正在开发一款麻将纸牌解决器，到目前为止，我做的还不错。然而，它并不是我想要的那么快，所以我要求任何额外的优化技术，你们可能知道。

所有的瓷砖都是从布局中知道的，但解决方案不是。目前，我没有什么规则可以保证安全地移除某些相同的瓷砖(这不能成为可能的解决方案的障碍)。

为了清晰起见，瓷砖在任何时候都是免费的，当它完全不绑定任何其他瓷砖时，瓷砖是松散的。

如果有四块免费的瓷砖可用，就把它们拆了-- immediately.

• If有三块可以拿起来，其中至少一块是松散的，拆下不松的瓷砖。

• ，如果有三块可以捡起，只有一块免费的瓷砖(两块)，就取下自由的和随意的一块。

• ，如果有三块松动的瓷砖，就移除其中的两块(不管哪一块)。

• ，因为有四倍的相同，如果剩下两块，把它们移除，因为它们是剩下的唯一了。--

我的算法递归地在多个线程中搜索解决方案。一旦一个分支被完成(到一个没有移动的位置)，并且它没有导致一个解决方案，它就把这个位置放在一个包含坏的向量中。现在，每当一个新的分支被启动，它将迭代通过坏的位置来检查，如果那个特定的位置已经被检查过了。

此过程将继续进行，直到找到解决方案或检查所有可能的位置。

这在包含36或72块瓷砖的布局上工作得很好。但是当有更多的时候，这个算法变得非常无用，因为有大量的位置需要搜索。

因此，我再问一次，如果你们中的任何人有好的想法，如何实现更多的规则，以安全清除瓷砖或任何其他特定的速度有关的算法。

向你问好，nhaa123

Answer 1

我不完全明白你的解决者是怎么工作的。当你有选择的动作时，你如何决定先探索哪一种可能性？

如果你选择一个任意的，它是不够好的-这只是野蛮的搜索，基本上。您可能需要先探索“更好的分支”。要确定哪个分支“更好”，您需要一个评估位置的启发式函数。然后，您可以使用一种流行的启发式搜索算法。检查一下这些：

• A*搜索
• 波束搜索

(谷歌是你的朋友)

Answer 2

几年前，我写了一个通过窥视解决纸牌麻将板的程序。我用它来检查一百万只海龟(在半台电脑上花了一天或什么时间:它有两个核)，看来其中大约有2.96 %无法解决。

http://www.math.ru.nl/~debondt/mjsolver.html

好的，这不是您所要求的，但您可能需要查看代码，以便在其中找到一些到目前为止还没有想到的剪枝启发式。这个程序不会使用超过几兆字节的内存。

Answer 3

不要使用包含“坏”位置的向量，而是使用具有常量查找时间的集合，而不是线性查找时间集。