Finding optimal algorithm for constructing biggest square from colored tiles

I've got N square tiles. Each side of 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?

-
Tell me if i'm wrong, but your first example is not right since 1E != 4W –  Ricky Bobby Oct 13 '11 at 11:12
Yes you are right, thx; Now it is correct. –  Zaphood Oct 13 '11 at 11:15
Is this for the Eternity 2 problem? en.wikipedia.org/wiki/Eternity_II_puzzle –  ypercube Oct 13 '11 at 12:04
Nope, but looks like its quite similiar, but simplified. I rather not expect more than 64 tiles, there are only 3 colors and orverall less restrictions so it shouldn't be that complex. –  Zaphood Oct 13 '11 at 13:12
@Zaphood, no, it's not correct! 2E != 3W! –  TMS Oct 13 '11 at 15:25
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}