Skip to content

Instantly share code, notes, and snippets.

@christianp
Created December 19, 2011 17:52
Show Gist options
  • Save christianp/1498143 to your computer and use it in GitHub Desktop.
Save christianp/1498143 to your computer and use it in GitHub Desktop.
Flipping squares puzzle
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)))
@christianp
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment