forked from darius/goobergram
-
Notifications
You must be signed in to change notification settings - Fork 0
/
boolean_constraints.py
41 lines (37 loc) · 1.26 KB
/
boolean_constraints.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
"""
Trivial implementation of Boolean constraints. The main constraints
module is supposed to be usable for many kinds of constraint networks,
not just the linear equations used by linogram -- so let's try out
defining another kind.
XXX untested
"""
from constraints import *
class BC(Constraint):
def __init__(self, variables, values):
# values is a collection of tuples, each with a boolean for
# each variable, corresponding to the variables in sorted
# order.
self.variables = frozenset(variables)
self.values = frozenset(values)
def solve(self):
for variable, value in solve(self.connected_constraints()):
variable.assign(value)
def get_variables(self):
return self.variables
def allows(self, asgn):
t = tuple(val for v, val in asgn if v in self.variables)
return t in self.values
def solve(bcs):
vars = set().union(*[bc.variables for bc in bcs])
for asgn in assignments(sorted(vars)):
if all(bc.allows(asgn)):
return asgn.items()
return ()
def assignments(vars):
if not vars:
yield ()
else:
v = vars[0]
for asgn in assignments(vars[1:]):
yield ((v, False),) + asgn
yield ((v, True),) + asgn