瓷砖贴合/排列的快速方法

Question

例如,假设我们有一个有界的2D网格,我们想要覆盖相同大小的方形图块.我们拥有无限数量的瓷砖,这些瓷砖属于规定数量的类型.每种类型的图块都指定印在该图块上的字母.在每个边缘旁边打印字母,并且只有在其相邻边缘上具有匹配字母的贴片可以在网格上彼此相邻放置.瓷砖可以旋转.

给定网格和图块类型定义的大小,排列图块的最快方法是什么,以满足上述约束并覆盖整个/大部分网格？请注意,我的用例适用于大型网格(每个维度约20个)和中等大量解决方案(与Eternity II不同).

到目前为止,我已经尝试了DFS从中心开始并选择填充区域周围的位置,这些位置允许最少的可能性和回溯,以防无法取得进展.这仅适用于具有一种或两种类型的简单方案.随之而来的是更多和太多的回溯.

这是一个简单的例子,显示输入和最终输出:

Answer 1

这是一个难题.

的永恒2是这样的形式与16×16正方形网格的一个难题.

尽管有200万美元的奖金,但几年内没有人找到解决方案.