The Dov problem

dov.py

# Counting Squares Problem
# Code derived from original script by Keith Brafford
#
import itertools

coords = [(0,0),   (1,0),           (2,0),              (3,0),   (4,0),
                        (1.5,.5),   (2,.5),   (2.5,.5),
         (0,1),   (1,1),(1.5,1),   (2,1),    (2.5,1),  (3,1),   (4,1),
                       (1.5,1.5),  (2,1.5),  (2.5,1.5),
         (0,2),   (1,2),           (2,2),              (3,2),   (4,2),
                       (1.5,2.5),  (2,2.5),  (2.5,2.5),
         (0,3),   (1,3), (1.5,3),  (2,3),    (2.5,3), (3,3),    (4,3),
                       (1.5,3.5),  (2,3.5),  (2.5,3.5),         
         (0,4),   (1,4),          (2,4),             (3,4),     (4,4),]
   
def forms_square(points):
    # Create a set of all X and a set of all Y values in the candidate quadrilateral
    x,y = map(set, zip(*points))
    
    if len(x) == 2 and len(y) == 2:
        return abs(x.pop() - x.pop()) == abs(y.pop() - y.pop())
    else:
        return False

points_iterator = itertools.combinations(coords, 4)

num_squares = 0
for potential_square in points_iterator:
    if forms_square(potential_square):
        num_squares += 1
        print num_squares, potential_square

num_squares -= 1 # One known "fake square"

print "%d Squares." % num_squares