# Identifying quad patterns in a two-dimensional array

In the tech demo I'm trying to make, tetrominoe-style blocks will be placed by the player, at which point the game checks to see if they've made a quad with any existing shapes on the board (a 2D array). If so, the quad should be processed in some way.

I have a 2D array like so:

``````[ [0, 0, 0, 1, 1, 1],
[0, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 1, 1],
[1, 0, 0, 1, 0, 1] ]
``````

And I need to identify 'quad' patterns such as that in the top-right corner, e.g.

``````[ [1, 1, 1],
[1, 1, 1],
[1, 1, 1] ]
``````

I'm not sure of the best way to do this. I've had a look at some two-dimensional array pattern matching algorithms, which all seem to flatten the 2D array into 1D, then use a 1D text searching algorithm (e.g. KMP) to identify any matches. My problems with that idea are that the quad can be any size, as long as it's rectangular and bigger than an arbitrary minimum (in my case, 2 x 2).

I also thought about using some variant of the 4 way flood fill algorithm or connected-component labelling, for each position of the newly-place tetrominoe. But I'm not quite sure how to best follow the path out and establish the bounds of a quad (for example, capturing this:

``````[ [1, 1, 1],
[1, 1, 1],
[1, 1, 1] ]
``````

out of this:

``````[ [1, 1, 1, 1],
[1, 1, 1, 0],
[1, 1, 1, 0] ]
``````

My latest though is perhaps a floodfill to get all interconnected parts after a tetrominoe lands, then 'round off' the jagged edges, maybe by checking the number of neighbours of each block, if it's 1, remove it, repeating the process until all remaining blocks have 2 or more neighbours. But this seems like it could be slow.

Has anyone any experience of this problem, or any pointers about how best to accomplish this task? I'm sure there's a common or at least applicable algorithm, I just don't know it!

-
Oh, brings back memories of my high school days at the IOI. I remember having solved this exact same problem with something like: for each cell, I store the maximum box I can make from this point by only going left and down; and I start filling this iteratively from the bottom left corner going up and right. The solution is O(n) for a total of n cells. I'll try coding it up later. – Panda Pajama Jan 25 '13 at 5:19
That'd be useful :) – codinghands Jan 25 '13 at 5:31

I drew it.

# What everything means

• Coloured backgrounds are the layout of filled squares just after a block has been placed.
• Red circles are locations that could potentially be the top-left corner of a quad.
• Red lines are on squares around a potential corner that must be filled for the shape to be a quad.
• Red crosses are locations that were checked and found to be empty. (In the last two diagrams, I've connected them to the red circle from which the check was made.)

# What happened?

In the first diagram (green), things worked out fantastically. The very first top-left corner we checked has filled squares on its bottom-right outline that form a `2x2` block. If we try to be even more ambitious and form a `3x3` block, we find that some of those (the red crosses) are not filled. So all we got is a `2x2`.

In the second diagram (blue), things worked out easily also. Except this time, even the second bottom-right outline matched on all squares: We have a `3x3` block. Trying for a `4x4` fails, as not all squares are filled.

In the third diagram (purple), we've got nothing. We ran out of filled squares to place the corner in before we found one that has a bottom-right outline.

In the fourth diagram (yellow), things worked after some trying. The first three squares we tried to place corners in had no bottom-right outline. The fourth, however, did. This gives us a `2x2`. Trying to get a `3x3` fails as in the first diagram.

# How would you implement this?

If your corner is `grid[0][0]`, the `n`th bottom-right outline consists of squares where one or both coordinates are `n`.

This generalises to: If your corner is at `grid[x][y]`, then the bottom-right outline is a union of these sets of squares:

• `grid[x+n][yVariable]`, where `y <= yVariable < y+n` (the right side)
• `grid[xVariable][y+n]`, where `x <= xVariable < x+n` (the bottom side)
• and finally `grid[x+n][y+n]` (the bottom-right corner)

It should be easy to iterate through these. If you have a quad, the top-right and bottom-right corners' coordinates tell you where it is.

That only works for squares though!

# Generalising to rectangles

Those three bullet points above can also be checked for individually:

This of course means that from any state of checking, 3 (instead of 1) possible further states may evolve:

Each of these three states can each be further expanded into up to three states by a similar method.

Your code could save the two other states for later and process the first to exhaustion before continuing with the next. At the end, the quad with the largest area would be the output. (This is, in computer science terms, a depth-first traversal of a trinary tree.)

-
Thank you for the comprehensive answer! I need some time to work through it, no doubt have some daft follow up questions :) really appreciated! – codinghands Jan 25 '13 at 11:11
Okay, a couple of things after some manic doodling in my pad... is there any way to generalise this for any rectangle shape (3 x 5, 2 x 4)? Also, is there a special case where we're checking grid[0,0] for a 2x2 grid (i.e. n = 1), as yVariable must break the constraint y < yVariable < y+n (y being 0, y+n being 1). Or not even a special case actually - to confirm a quad at grid[0,0], we need to check [0,1] (bottom), [1,0] (right) and [1,1] (bottom right). So yVar must be 0, equalling y... Though my maths is awful :( – codinghands Jan 25 '13 at 11:44
@coding Indeed, the inequality is a typo: I meant `y <= yVariable < y+n`! I'll fix that! – Anko Jan 25 '13 at 11:59
@coding I've edited the answer to cover rectangles, though in less depth. Is it intelligible? – Anko Jan 25 '13 at 16:03
I will review when it is not 4am and report back! – codinghands Jan 25 '13 at 17:48

Just as a follow up - I eventually ended up coding a couple of solutions, one of which was basically a Javascript implementation of the Maximal Rectangle algorithm described in this article on Dr Dobbs. Seems like my issue was basically the problem this algorithm aims to solve in a nutshell!

I've written up a short blog piece on how I did it in Javascript and the resultant code, available on my blog over here.

-