Finding optimal algorithm for constructing biggest square from colored tiles

I've got N square tiles. Each side o开发者_如何学JAVAf tile is colored in red, green or blue color. The goal is to form biggest possible square from tiles in such a way that adjacent edges are of same color.

Example 1: let N,W,S,E represent north, west, south and east tile side respectivly, and R,G,B represent colors. We got 5 tiles

  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

Example 2: We got 6 tiles

  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

Biggest possible square to build here is 1x1.

I will be developing application solving this task. What would be good algorithm to find the best solution in shortest time?

---

You can obviously find a solution by writing down a set of constraints on the tiles chosen to fit each location and then using backtracking search. I will be surprised if there is a better general solution, because it appears that you can encode very general problems as tiling problems - see http://en.wikipedia.org/wiki/Wang_tile