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 nth 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.

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 nth 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.)

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 nth 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.

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 nth 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.