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

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