尋找從彩色瓷磚構建最大正方形的最優算法

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