寻找用彩色瓷砖构造最大正方形的最优算法

Question

我有N个方块。瓷砖的每一面都是红色、绿色或蓝色。我们的目标是用瓷砖形成尽可能大的正方形，使相邻的边颜色相同。

例1:设N、W、S、E分别代表北、西、南、东瓷砖面，R、G、B代表颜色。我们有5块瓷砖

  N W S E
1 B R B R                                                           1 4
2 B G R B   i can form 2x2 square from it placing tiles like this   2 3 
3 B G G G
4 G R B R
5 G R B R

例2:我们有6块瓷砖

  N W S E
1 B B B B                                                           
2 B B B B   
3 G G G G
4 G G G G
5 G G G G
6 R R R R

这里最大的正方形是1x1。

我将开发解决此任务的应用程序。在最短时间内找到最优解的好算法是什么?

Answer 1

您显然可以通过写下一组适合每个位置的瓷砖的约束，然后使用回溯搜索来找到解决方案。如果有更好的通用解决方案，我会感到惊讶，因为您似乎可以将非常通用的问题编码为平铺问题-参见http://en.wikipedia.org/wiki/Wang_tile