IMHO this is very hard task - only 104 accepted solutions. My solution is here
Google gives lots of links for trominos but they all for totally different task from Euler Project - in our case we have only L-shapes. So lets think about possible algorithm
It`s pretty obvious that we can make 2 x 3 or 3 x 2 rectangles with couple of L-trominos. So naive solution is just to check if one size is divisible by 2 and other by 3
However with pen and paper you can quickly realize that you can for example fill rectangle 5 x 6:
aabaab
abbabb
ccddee
dcdced
ddccdd
Algo can look like (see function check2x3)
- if one side of rectangle is divisible by 6 then another minus 2 should be divisible by 3
- if one side of rectangle is divisible by 6 then another minus 3 should be divisible by 2
Submit our solution and from failed tests suddenly discovering that you also can have rectangle 9 x 5. Some details how this happens
So we can have maximal 3 groups of different shapes:
- 9 x 5 rectangle (or even several if sides multiples of 5 & 9) - in my solution it stored in field has_95
- 1 or 2 groups of 2 x 3 rectangles below 9 x 5 shape. 1 for case when you can fill this area with shapes 2 x 3 of the same orientation and 2 if you must mix vertical and horizontal rectangles - field trom
- the same 1 or 2 groups on right of 9 x 5 shape - field right
Now the only remained problem is coloring
Rectangle 9 x 5 has 5 different colors but it is possible to arrange trominos in such way that on borders it will have only 4 colors and 5th is inside. For groups of 2 x 3 rectangles you need 4 colors if group size is 1 and yet 4 if size is 2. In worst case number of colors is 4 for 9 x 5 + 2 * 2 * 4 = 20 - so we can fit in A-Z
