Finding shapes in 2D Array, then optimising

I've just been allowed an image...The image below from my game shows some darkened blocks, which have been recognised as being part of a "T" shape. As can be seen, the code has darkened the blocks with the red spots, and not seen the "T" shapes with the green outlines.

My code loops through x/y, marks blocks as used, rotates the shape, repeats, changes colour, repeats.

I have started trying to fix this checking with great trepidation. The current idea is to:

• loop through the grid and make note of all pattern occurrences (NOT marking blocks as used), and putting these to an array
• loop through the grid again, this time noting which blocks are occupied by which patterns, and therefore which are occupied by multiple patterns.
• looping through the grid again, this time noting which patterns obstruct which patterns

That much feels right... What do I do now?

I think I would have to

• try various combinations of conflicting shapes, starting with those that obstruct the most other patterns first.How do I approach this one?
• use the rational that says I have 3 conflicting shapes occupying 8 blocks, and the shapes are 4 blocks each, therefore I can only have a maximum of two shapes.

(I also intend to incorporate other shapes, and there will probably be score weighting which will need to be considered when going through the conflicting shapes, but that can be another day)

I don't think it's a bin packing problem, but I'm not sure what to look for. Hope that makes sense, thanks for your help

EDIT Despite clarity of question, everyone seems to have understood, yes,

I want to find the maximum "T" shapes within each colour

(because if I gave you points for two and you had made three, you'd be a bit annoyed)

-
A greedy algorithm coudld be to split the board up into collections of joined blocks. Then for each collection you could try ti fill with shapes and give the fill a score dependent on the amount of blocks left that wouldn't be darkened. Kind of makes me think of the en.wikipedia.org/wiki/Knapsack_problem. – Jonathan Connell Oct 8 '12 at 16:54
I think there's something missing in the question. Do you want to make an algorithm that finds as many "T" shaped groups as possible? – Markus von Broady Oct 8 '12 at 17:15
If I understand you then you are heading the right way. You are not exceedingly clear and I would love it if you could elaborate. – zehelvion Oct 8 '12 at 17:39

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:

http://sourceforge.net/projects/lpsolve/

(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:

1. Find all possible Line shapes
2. Find all intersections between line shapes of the same color
3. Find all possible T shapes, searching all intersection.
4. 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.
5. Make the conditions for each couple of T shapes that intersect (`Bi + Bj <= 1`)
6. The objective function will be (sum of blocks in "T" Shape (i) * Bi)
7. 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:

http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns

This explains it well:

http://fisher.osu.edu/~croxton_4/tutorial/

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.

-
Thank you Arthur for your help. It might take a couple of reads to digest. And yes, you understood the problem correctly. I'd be very interested if you were to elaborate (no, no it's not trivial), but this should help me get where I'm going! – Assembler Oct 9 '12 at 1:27
Which language are you using for the implementation? – zehelvion Oct 9 '12 at 4:21
actionscript 3! everyone's favourite! – Assembler Oct 9 '12 at 4:50
same here. I will write an implementation in as3 and upload it into a github for download with commentation, working step by step - I can get it done later today – zehelvion Oct 9 '12 at 5:04
Do you have any specific areas 1 -7 where you would like me to add more comments or elaborate? btw, good news for us AS3 lovers, Adobe released FlasCC which supports C++ so we can use existing linear solvers with ease. :) – zehelvion Oct 9 '12 at 20:56

Once you have a list of all (possibly overlapping) T-shapes occurring in your grid, what you're left with is a maximum set packing problem.

In general, this is an NP-complete problem. However, your grid is small enough (and typically breaks up into even smaller independent subproblems) that it may well be feasible to obtain exact solutions.

Addendum: Here's a basic backtracking search algorithm that might do the trick:

``````function max_packing_recursive ( set A, set S, set M ):
if |M| < |S| then let M = S;
for each shape X in A do:
remove X from A;
let B = A;
remove all shapes that intersect with X from B;
if |M| < |B| + |S| + 1 then:        // upper bound
let M = max_packing_recursive( B, S + {X}, M );
end if
if |M| >= |A| + |S| then return M;  // shortcut
end for
return M;
end function

function max_packing( set A ):
return max_packing_recursive( A, {}, {} );
end function
``````

Here, `{X, Y, Z}` denotes the set containing the elements `X`, `Y` and `Z` (with `{}` being the empty set), and `|Q|` denotes the size of the set `Q`.

In the recursive function, the set `A` contains the shapes available for the remaining solution, `S` contains the shapes in the current solution candidate, and `M` is the maximal solution so far (which you may want to store as a global variable instead of returning it back up the call chain). The important optimization is on the line marked with `// upper bound`, which prunes branches of the search tree that cannot possibly return a better solution than `M`.

(Actually, since we know that each T-shape contains exactly four sites, a much better upper bound could be obtained by replacing `|B|` with the number of distinct sites covered by the shapes in `B`, divided by four and rounded down (and similarly for `|A|` on the line marked with `// shortcut`). The algorithm as given above, however, works for arbitrary collections of shapes.)

A possible additional optimization, which I haven't implemented above, would be to check at the beginning of the recursive function whether `A` divides into multiple subsets that are independent, in the sense that no shapes in different subsets overlap, and if so, apply the algorithm to each of the subsets separately. (In any case, you'll definitely want to do this at least once at the top level before calling the recursive algorithm.) Sorting the shapes in `A` appropriately before looping over them, e.g. in increasing order by number of overlapping shapes, could also help.

-
Yeah, I think he could use a ILP to solve it relatively painlessly because of the size of the problem.. 2^20 ~= 1,000,000 so since there can only be so many T shapes, he should be fine using a linear solver for this. It is clearly exponentially complex(At least until someone manages to prove that p = np). The size allows avoiding heuristics in this relatively simple case. – zehelvion Oct 8 '12 at 17:53
Ilmari, thank you very much. This answer too will take a few goes to understand. The arbitrary shapes bit may well be useful in future iterations. – Assembler Oct 9 '12 at 1:27