====== Recognizing and Counting Squares ======

There is a **puzzle** figure that has been circulating on a social web site for a while, with the question "How many squares do you see?"

{{:square_0.jpg|}}

There are at least three answers which might be considered correct, depending on what **rules** are assumed.

  - Only "flooding" is allowed: one colors each zone up to its boundaries, and counts the zones that are squares.
  - Composition is allowed: k*k regions composed of identical squares can be counted.
  - Any square boundary is allowed; no matter what is inside, how the zone within the boundary is divided, the squareness of the boundary is all that matters.

===== Flooding =====

The first solution is to count all the squares with nothing else in them. In the puzzle figure, we count 16:

{{:square_1.jpg|}}

===== Composition =====

If we allow composition by merging k*k blocks of squares, we can add two more to our count. Notice, however, that the area between the first and last columns (squares 1-8) are not composed of blocks of squares after this merger because the two additional squares are offset.

{{:square_2.jpg|}}

===== Arbitrary Square Boundaries =====

This allowance will enable us to remove the minisquares that we merged to form the two offset squares, producing eight more squares immediately. It also results in a 4*4 grid, which has many more possible k*k compositions.

==== Eliminating (Ignoring) Non-Corner Inner Zones ====

Deriving from the previous figure, with squares 17 and 18 centered in larger (2*2) squares, eliminate those inner zones to clear the two larger (not yet counted) squares:

| {{:square_2b.jpg|}} |

==== Eliminating (Ignoring) Corner Inner Zones ====

Deriving from the first figure, with squares 1 to 16, remove (ignore) mini-squares 9 to 16, clearing squares 21 to 28 in columns two and three:

| {{:square_2a.jpg|}} |

  * The count is now at least 28, with several more to come through composition.

==== 2 * 2 Blocks ====

The blocks 19 and 20 already "discovered" are the first two of nine 2*2 squares. Here are the seven others:

^ Four corners| {{:square_3a.jpg|Corner 2x2s}} |
^ Central Horizontal| {{:square_3b.jpg|Horizontal 2x2s}}  |
^ Center| {{:square_3c.jpg|Central 2x2}} |  |

    * The count is up to 35.
 
==== 3 * 3 Blocks ====

Four 3*3 blocks can be composed from the 4*4 grid,
^  ^  Left  ^  Right  ^
^ Top| {{:square_4a.jpg|Top left 3x3}} | {{:square_4b.jpg|Top right 3x3}} |
^ Bottom| {{:square_4d.jpg|Bottom left 3x3}} | {{:square_4c.jpg|Bottom right 3x3}} |

  * The count is now 39, with the outer box yet to count.

==== 4 * 4 Block ====

{{:square_5.jpg|Outer square}}

===== Final Tally =====

^ Rule  ^  Contribution  ^  Running Tally ^
^ Flooding  |  16  |  16  |
^ Flooding, composition |  +2  |  18  |
^ Non-block merging: squares in corners  |  +8  |  26  |
^ Non-block merging: inner contained zones (result 2*2) |  +2  |  28  |
^ Further 2*2 compositions  |  +7  |  35  |
^ 3*3 compositions  |  +4  |  39  |
^ 4*4 composition   |  +1  |  40  |