gistfile1.py

from itertools import *
from collections import defaultdict

a = 3
b = 6

verts = [(x,y) for x in range(1,a+1) for y in range (1,b+1)]

adjacent = defaultdict(list)
for v1 in verts:
    for v2 in verts:
        if (v1[0]-v2[0]) * (v1[0]-v2[0]) + (v1[1]-v2[1]) * (v1[1]-v2[1]) == 5:
            adjacent[v1].append(v2)

print sum([len(adjacent[x]) for x in adjacent])/2;

paths = defaultdict(list)
pathsbetween = {}

bigdegverts = [v for v in verts if len(adjacent[v])>2]
print "deg3: "
print len([v for v in verts if len(adjacent[v])>2])
print len(bigdegverts)

def paths_from_recurse(paths):
    new_paths = []
    for path in paths:
        for next in adjacent[path[-1]]:
            if next not in path and path+[next] not in paths:
                new_paths = new_paths + [path+[next]]
    if new_paths==[]:
        return paths
    else:
        return paths_from_recurse(paths+new_paths)

#this function is from the python docs
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def paths_from(v0):
    return paths_from_recurse([[v0]])
'''
print "computing paths..."
for v in verts:
    paths[v] = paths_from(v)

print "paths computed, computing interpaths:"

for v1 in verts:
    paths1 = paths[v1]
    print (v1,v2)
    for v2 in verts:
        paths2 = paths[v2]
        pathsbetween[(v1,v2)] = [x for x in paths1 if list(reversed(x)) in paths2]
'''
#print "done computing interpaths"

#print "paths between:"

i=0;
print 'iterating'
for c6 in combinations(bigdegverts,6):
    print i
    i=i+1
    for c3 in combinations(c6,3):
        red = c3
        blue = filter (lambda x:x in c6 and x not in c3, c6)
        #print red
        #print blue

        for adj_subset in powerset(adjacent):
            adj_subset_lst = list(adj_subset)
            adj_subset = dict(adjacent)
            for x in verts:
                if x not in adj_subset_lst:
                    for y in adj_subset[x]:
                        if x in adj_subset[y]:
                            adj_subset[y].remove(x)
                    adj_subset[x] = []

            #print adj_subset
            for v in verts:
                if len(adj_subset[v])==2:
                    for x in adj_subset[v]:
                        adj_subset[x] = adj_subset[x]+adj_subset[v]
                        if (v in adj_subset[x]):
                            adj_subset[x].remove(v);
                    adj_subset[v]=[]
            
            flag=True

            for r in red:
                for b in blue:
                    if (b not in adj_subset[r]):
                        flag=False
            
            if flag:
                print "found k3,3:\n"
                print red
                print blue
                exit()

print i