#!/usr/bin/pyhton

# Solver for the Lights Out game
# http://en.wikipedia.org/wiki/Lights_Out_(game)
# 
# released under the GPL

# each problem has only 2^25 potential solutions
# we can brute-force it in a few minutes (not very elegant, I admit)
# 
# furthermore, the trivial problem has exactly four solutions
# (and this program can prove it by exhaustive search)
# so every problem has exactly four solutions
# 
# to put it differently, the group of the solutions of each problem is a 
# subgroup of all possible solutions, isomorphic to the (Z/2Z)^2


# lights are numbered from 0 to 24
# any convention can be chosen, the only rule is to be consistent

# conversion between [0..24] and [0..4]x[0..4] notation
def coordsFromId(i):
	return divmod(i, 5)
def idFromCoords(x, y):
	return x * 5 + y

# I am too lazy to hardcode this
def neighbours(i):
	'''Returns a list of the neighbours of light i'''
	r = [i]
	x, y = coordsFromId(i)
	if (x > 0):
		r.append(idFromCoords(x - 1, y))
	if (x < 4):
		r.append(idFromCoords(x + 1, y))
	if (y > 0):
		r.append(idFromCoords(x, y - 1))
	if (y < 4):
		r.append(idFromCoords(x, y + 1))
	return r

# list of the lights to switch when light number i is switched, including i
nb = [neighbours(i) for i in range(25)]

def switchLight(i):
	'''Updates the board when a light is switched
	
	also updates solution'''
	for j in nb[i]:
		board[j] = not board[j]
	solution[i] = not solution[i]

# initial problem
# True = light on, False = light off
board = [False for i in range(25)]

# Set your problem here (or write an input function)
# example:
# board[idFromCoords(1, 1)] = True
# board[idFromCoords(1, 3)] = True

# solution for this problem
# True = switch this light, False = don't touch
solution = [False for i in range(25)]
# list of all possible solutions
solutions = []

def checkSolution():
	'''Tests if the problem is resolved
	
	relies on the contents of board
	adds solution to the list of known solutions if necessary'''
	if True in board:
		return False
	else:
		solutions.append([solution[i] for i in range(25)])
		return True

def iterateSearch(n):
	'''Iterates recursive search
	
	n first values of solution are fixed
	tries the two possible values for solution[n] and iterates'''
	
	if n == 25:
		# end of iteration, do we have a solution?
		checkSolution()
	else:
		# explore both branches
		iterateSearch(n+1)
		switchLight(n)
		iterateSearch(n+1)
		switchLight(n)
		# re-switching is mandatory since we use a global variable
		# that must be left unchanged after executing the function

# start search
iterateSearch(0)

# sort solutions by inscreasing length
solutions.sort(lambda x, y: len(x) - len(y))	# python 2.3
# in python 2.4, use solutions.sort(None, len)

# print results

def prettyPrint(data):
	print "+---+---+---+---+---+"
	for x in range(5):
		for y in range(5):
			if (data[idFromCoords(x, y)]):
				print "| O",
			else:
				print "|  ",
		print "|"
		print "+---+---+---+---+---+"

print "Problem"
print ""
prettyPrint(board)
print ""

print "Solutions"
for s in solutions:
	print ""
	prettyPrint(s);