Flipping squares puzzle

flip.py

from itertools import product
from operator import mul
from functools import reduce
from math import log

#represent the state of the board with a binary string of 9 digits
#the states form a group under XOR on each cell - 
#when combining states S1 and S2, a cell is lit up iff it is lit up in S1 XOR it is lit up in S2
#states commute: S1.S2 = S2.S1, because XOR commutes
#additionally, note that for every state S, S.S = 0.

#this class represents a state of the board (element of the group)
class State:
    def __init__(self,state):
        self.state = state

    #This function combines two states and returns the resulting state
    def __mul__(s1,s2):
    #   what this is doing is taking s1_ij XOR s2_ij for each cell (i,j)
        return State(''.join([str(int(x)^int(y)) for x,y in zip(s1.state,s2.state)]))
    #                           ^                       ^
    #                       x XOR y                 pairs (s1_ij, s2_ij)

    #test if two states are equal
    def __eq__(s1,s2):
        return s1.state==s2.state

    #hash a state - used by the Set data type. We just need to return an integer unique to this state
    def __hash__(self):
        m=0
        for x in self.state:
            m=m*2+int(x)
        return m

    #helper function to display a state as a 3x3 grid.
    def __repr__(self):
        return '\n'.join([self.state[x:x+3] for x in range(0,9,3)])

def makegens(n):
	gens=[]
	d1,d2='',''

	for i in range(0,n):
		gens.append(('0'*i+'1'+'0'*(n-i-1))*n)			#flip column i
		gens.append(('0'*n)*i+('1'*n)+('0'*n)*(n-i-1))	#flip row i
		d1+='0'*i+'1'+'0'*(n-i-1)						#first diagonal: flip cell i in row i
		d2+='0'*(n-i-1)+'1'+'0'*i						#second diagonal: flip cell n-i in row i
	gens+=[d1,d2]
	return [State(x) for x in gens]

grid_size=int(input('Size of grid: '))
gens=makegens(grid_size)

#The question is: do they form a basis set for all possible states?
#Straightforward answer is no: there are 2^9 possible states, and we're only given eight generators, so they can produce at most 2^8 states (since states commute and have order 2)
#So we'll test that, but we'll also ask: is this an independent set of generators? Can any of these states be obtained by a combination of the others?

#work out the set of all possible states
binstrings = product([True,False],repeat=len(gens))             #get all the binary strings with as many digits as we have generators
words = [[x for x,y in zip(gens,b) if y] for b in binstrings]   #get the words corresponding to those binary strings - use a generator if the relevant binary digit is True
states = [reduce(mul,word,State('0'*grid_size*grid_size)) for word in words]      #for each word, multiply all its letters together to get the equivalent state. (State('0'*9) is the initial state, with all cells set to 0)
states=set(states)                                              #chuck out duplicates

print('%s states generated by the given moves' % len(states))   #report how many states we can make with the given generators!
print('So %s independent moves' % int(log(len(states),2)))

In answer to this problem: http://i.imgur.com/mLHGc.jpg