I like these puzzles, but they all seem to be solvable with a simple algorithm:
To solve the puzzle of finding the number of squares (or other figures) in an incomplete grid:
1. DEFINITIONS:
GRID: a set of equal-length line segments that connect at right angles.
CORNER: a point at which the line segments connect
SIDE OF LENGTH X: a set of line segments that connect in a straight line. Example: a side of length 3 is 3 line segments connecting in a straight line.
COLUMN: a vertical (as seen by the viewer) set of corners. These need not all be connected by line segments. (Missing line segments complicate the problem to be solved).
ROW: a horizontal row of corners. As with columns, these need not all be connected by line segments. LEFT, RIGHT, TOP, BOTTOM: all have the commonly accepted meaning.
COUNT-OF-SQUARES: initialize as 0, because there might not be any.
I, J, K = counters; don't worry about them yet
Let NR = number of rows of corners
NC = number of columns of corners
2. COUNT PROCEDUREFor I=1 through (NC minus 1):
For J=1 through (NR minus 1):
For K=1 through (NC minus 1):
If the 4 corners (I, J), (I, J+K), (I+K, J), (I+K, J=K) are all connected by an unbroken set of line segments, add 1 to COUNT-OF-SQUARES.
ENDIF
ENDFOR
ENDFOR
ENDFOR.
The value of COUNT-OF-SQUARES is now the value sought.
2. RECTANGLES:
A similar method works except that you have to allow for different numbers of rows and columns. This is not a difficult change.
3. OTHER SHAPES:
The same general methods works for triangles, hexagons, mickey-mouse ears, etc. Basically, find a feature such as one or more corners that uniquely defines the thing to be tallied, and scan each feature for each other feature that defines a unique instance of the shape.
--
I had previously blogged a simpler solution for a smaller set of problems, but when this one started circulating in my Facebook feed, I felt impelled to write up the more general solution I had been thinking of for a while. Maybe I won't lose this one among all the blog posts!
