Let me see if I got it right, the red marked blocks, were blue and the algorithm found a T shape and marked them red, is that correct? Your goal is to find as many T shapes as possible with same colored blocks, correct so far I hope. Currently you mark them out once you find them and that diminishes the usefulness of the algorithm(Since you could be missing the optimal solution). You are planning on searching for all shapes and then picking which ones to use and which one not to use. Am I correct so far? Cause you wish to maximize the amount of blocks that are contained inside the T shapes when the algorithm is done.
If I am correct the following is the optimal solution for your situation in my opinion.
We will use Integer Linear Programming.
I believe I used this one in the past:
(You can get it to work with many languages, I used it with PHP, Java and C)
What we will do is register every possible T shape on the board and then use ILP to maximize the amount of blocks that are covered.
ILP is exponentially complex. Considering the size of your board, that will not be a problem. I have ran much more complicated min/max questions on graphs with ILP and it only took a fraction of a second to complete and up to 30-90 seconds with hundreds of vertices(in your case it falls in the fraction of a second).
What I would recommend to do:
- Find all possible Line shapes
- Find all intersections between line shapes of the same color
- Find all possible T shapes, searching all intersection.
- Define a Boolean variable in the Linear Problem for each T shape (
0 <= Bi <= 1) Since the values are integers, that leaves 0 or 1.
- Make the conditions for each couple of T shapes that intersect (
Bi + Bj <= 1)
- The objective function will be (sum of blocks in "T" Shape (i) * Bi)
- Run the solver and darken the T shapes where the solver's corresponding Boolean(s) where 1 in the optimal solution.
This is valuable knowledge, I used linear solvers often for work projects.
ILP is basically a way to solve selection problems where you want to achieve a maximum or a minimum for some linear function.
You can read more here, using Integer Linear Programming and Linear Programming is the same for the programmer only that Integer is far more complex for the computer which may result in long running times. Not in your case, It is very simple and should only takes less than milliseconds in the worst case.
I guess you could read more here:
This explains it well:
It is basically a decision problem solver, how to make decisions that maximize the result you want. This assumes the function that judges the result is linear which in your specific current case it is. The function that judges the result in this case, sums up the blocks for all the T shapes you decided to darken.
Mathematically, how to set the variables: in our current case Booleans(Did I darken T shape with index i or not) to the optimal values to maximize the result we want: darkening as many blocks as possible without darkening intersecting T shapes. As long as the result you want can be calculated with a linear function when you have all the variables set it will solve it. In our case, we check which T shapes we darkened and sum the blocks they cover.
I know this is not trivial so if you choose to take the leap, feel free to comment and I will elaborate.