The Dov problem

dov.py

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):
    xd = {}
    yd = {}

    for x,y in points:
        xd[x] = xd.get(x,[])
        xd[x].append(1)

        yd[y] = yd.get(y,[])
        yd[y].append(1)

    return all((len(xd.keys()) == 2, len(yd.keys()) == 2))


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