Skip to content

Instantly share code, notes, and snippets.

@smaspe
Last active January 6, 2016 20:28
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save smaspe/bb7efc8e03e8eaa81629 to your computer and use it in GitHub Desktop.
from collections import Counter
size = 11
tab = [None] * size*size
def split(t):
return [t[size*i:size*i+size] for i in range(size)]
def splitV(t):
return [t[i::size] for i in range(size)]
not_none = lambda x: x is not None
calls_counter = 0
inconsistencies_counter = 0
def solve(t):
global calls_counter
global inconsistencies_counter
calls_counter += 1
cnt = Counter(sum(filter(not_none, row))
for row in split(t)
if len(list(filter(not_none, row))) == size)
cnt += Counter(sum(filter(not_none, col))
for col in splitV(t)
if len(list(filter(not_none, col))) == size)
if len(cnt) == size * 2:
# OK
return t
if len(cnt) > 0 and cnt.most_common(1)[0][1] > 1:
# Inconsistency
inconsistencies_counter += 1
return None
for val in [-1, 0, 1]:
tt = t[:]
if None not in t:
print t
tt[t.index(None)] = val
res = solve(tt)
if res:
return res
return None
print(solve(tab))
print(calls_counter, inconsistencies_counter)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment