Take the 2-minute tour ×
Puzzling Stack Exchange is a question and answer site for those who study the creation and solving of puzzles. It's 100% free, no registration required.

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

enter image description here

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

share|improve this question

5 Answers 5

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

share|improve this answer
    
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 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 at 19:48

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

share|improve this answer

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.

share|improve this answer

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

enter image description here

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.

share|improve this answer

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
share|improve this answer
    
Is this the same as mine but with code? I agree that it seems less likely to error than others. –  kaine Jun 12 at 19:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.