# When to be sure that we have counted all the squares in such problems

My first question: how would one solve such problems (in general)? What should be the general technique?

My second question: When to be sure that we have counted all the squares in such problems?

-

You need to find some systematic technique. The technique will depend on the problem. Usually there is a regularity to the problem that you can exploit. In this case, I would note that the two squares that are not part of the main $4 \times 4$ do not interact with the lattice, so we can count them separately. For the lattice, work by square size. You have four choices along each edge for the upper left corner of a $1 \times 1$ square for $16$ in total. Similarly there are $9\ 2 \times 2$ squares, $4\ 3 \times 3$ squares and $1\ 4 \times 4$ for a total of $30$. You might even know that in an $n \times n$ chessboard there are $\sum_{i=1}^ni^2=\frac 16n(n+1)(2n+1)$ squares. Each of the stray squares gives us five, for a total $40$.

-
My only issue with this answer (though I did vote it up) is that there is some risk of error is the problem is difficult to parse into smaller chessboards or someone is confused by overlapping ones. Nevertheless if broken up correctly this is much faster than an brute for method. Maybe an example of a chessboard with one interior line missing might formalize it better. – kaine Jun 12 '14 at 19:41
@kaine: I agree there is a risk of error. When these are given as puzzles, you are usually expected to count by hand and there are strong patterns to make use of. In a sense, that is what makes them good puzzles. One can ask the same question for less regular layouts, when the proper approach is a computer search. They wouldn't be any fun by hand and the chance of error is greater. Your answer is a good outline for such a program. – Ross Millikan Jun 12 '14 at 19:48

Systematic technique is definitely required. I came across this particular puzzle a few years ago on facebook and got into arguments with some people about the answer, with them arguing that there were 41, 42 or even more squares. Eventually I got bored, produced this animation

which shows 40 different squares, and challenged them to show me one that I'd not highlighted.

The general case would be similar - find the recurring pattern, and count them methodically.

As to knowing if you've "found them all", that's just down to being rigorous and methodical in your search. This can get difficult if the puzzle is particularly complex or large, but if the answer is in the realms of "easily countable" as it is in this case then this is easily verified manually.

-

One potential strategy is as follows:

Call this example an square of dimentions 8x8

1. Start from an extreme corner of the diagram. (example: top left corner)
2. Iterate across the board in such a way as to cover the entire board (example: move down 8 units, right 1 unit, up 8 units, right 1 unit and repeat)
3. Each time you reach previously chosen corner type count the number of possible opposite corners and ensure that they all make a square. (exampe: Each time one sees a "bottom left" corner, draw a line segment of slope 1 towards the top right. Count the number of "top right" corners that this line intersects. Eliminate from this count any corner pairs that have broken sides.)
4. Continue until the entire map is covered and all squares counted.

By this strategy I get:

40 squares

-

Another strategy would be as follows:

1. How many 1x1 squares can we have, ignoring the smaller squares? 4 rows of 4 --> 16
2. How many 2x2 squares can we have, ignoring the smaller squares? 3 rows of 3 --> 9
3. How many 3x3? 2 rows of 2 --> 4
4. How many 4x4? 1 --> 1

This gives us (16+9+4+1)=30 squares.

Now add in the smaller squares:

1. How many 1x1 can we have? 8
2. How many 2x2? 2

This gives us 10 more squares. Add those answers and we get 40.

-

I believe the 98% get it wrong because of the fact that the question itself is a square. They count the 40 squares created by the green lines, but they miss the pink square. @ClickRick, I believe those that say 42 are correct: the pink area makes 41, the embossed rim would make 42. However, if you wanted to go further, you could note that the background is two different colors; pink and purple, slightly different tones. I count at least 13 purple squares in the background, and at least 2 pink ones. The problem is that the rules are not clearly defined; 40 is correct from a basic standpoint, looking at only the green lines. However, since 98 percent get it wrong, and it is a puzzle after all, I must believe that the squares that exist outside of the line are meant to be counted. My guess is that a large portion of the 98 percent probably say 40. In your simulation, there are only 40. But I believe that there is some reason for the pink background, rather than a plain white one - to complicate things, creating additional inconspicuous squares.

-
And the obligatory XKCD link – Trevor Powell May 18 '15 at 11:45

Answer to question 1 and 2: Use brute force, that means test all possible combinations.

You will need a definition to check if a point exists and if a line exists.

In Pseudocode that looks something like this:

function get_square_count()
counter = 0
for each a in corners:
for each b in corners:
//same height level and b right of a
if a.x=b.x and a.y<b.y:
if is_square_top_line(a,b):
counter++
return counter

function is_square_top_line(a,b)
// use square property to add height
calculate virtual points c,d
check if c and d exist
check if all lines exists a,b b,c c,d, d,a

-
Is this the same as mine but with code? I agree that it seems less likely to error than others. – kaine Jun 12 '14 at 19:39