好吧,我正在考虑制作一个Tetravex求解程序,以便练习我的代码编写技巧(语言可能是Visual Basic),我需要帮助找到解决它的算法.对于那些不知道tetravex是什么的人,请参阅http://en.wikipedia.org/wiki/TetraVex.我能想出的唯一算法是蛮力方式,在一个角落随机放置一块瓷砖并尝试旁边的每一块可能的瓷砖并继续相同的过程,如果到达死角,则恢复到之前的状态并放置一个不同的瓦.那么有人能提出更好的算法吗？感谢您的时间.
这里有一些想法。
普通的强力算法会尝试通过以固定顺序枚举网格位置（例如行主）来递归地填充网格，并始终尝试将每个可能的块放入当前位置，然后递归。这就是你提到的，效率很低。
一种改进是始终计算每个空闲位置适合该位置的件数，然后递归到适合最少的位置；如果配件件数为零，则立即原路返回；如果只有一件适合，则填充并继续（不创建分支）；否则选择具有最少拟合件 (≥ 2) 的一个并从那里继续。
一旦你有了这个算法，下一个问题就是如何进一步修剪搜索空间。比如说，如果有 A 件在顶部位置为“1”，B 件在底部位置为“1”，并且 A > B，那么您知道“1 在顶部位置”件中至少有 A - B必须实际放置在顶行，因此您可以将它们排除在任何其他位置。这有助于减少分支因子并更早发现死胡同。
您还应该在每个递归步骤中检查每个片段是否至少有一个适合的位置（在验证没有片段仅适合一个位置以提高速度后执行此检查）。如果有一块不适合任何地方，您需要立即原路返回。您可以将其扩展到检查每对部件是否适合可能更好的早期死锁检查功能。
还有一种策略称为“非时间顺序回溯”或“回跳”，源自对 SAT 求解的研究。这可以帮助您在遇到死胡同时一次回溯多个级别；如果您愿意，您可以通过谷歌搜索这些术语来查找更多信息，但是您需要做一些脑力工作才能将概念映射到您的问题空间中。