Code repository for tutorial on constraint programming available on https://mareknarozniak.com/2020/06/22/constraint-programming/
from constraint import Problem | |
problem = Problem() | |
problem.addVariable('x', range(1, 10)) | |
problem.addVariable('y', range(1, 10)) | |
problem.addVariable('z', range(1, 10)) | |
def constraintCheck(x, y, z): | |
if x**3 + y**2 - z**2 == 0: | |
return True | |
return False | |
problem.addConstraint(constraintCheck, ['x', 'y', 'z']) | |
solutions = problem.getSolutions() | |
for solution in solutions: | |
print(solution) | |
x = solution['x'] | |
y = solution['y'] | |
z = solution['z'] |
from constraint import Problem | |
import pprint | |
pp = pprint.PrettyPrinter(indent=4) | |
f = frozenset | |
towns = { | |
'Indigo Plateau': 'a', | |
'Pallet Town': '', | |
'Viridian City': '', | |
'Pewter City': '', | |
'Cinnabar Island': '', | |
'Cerulean City': '', | |
'Saffron City': '', | |
'Celadon City': '', | |
'Lavender Town': '', | |
'Vermillion City': '', | |
'Fuschia City': '', | |
'Special Region': '' | |
} | |
V = f({ | |
'Indigo Plateau', | |
'Pallet Town', | |
'Viridian City', | |
'Pewter City', | |
'Cinnabar Island', | |
'Cerulean City', | |
'Saffron City', | |
'Celadon City', | |
'Lavender Town', | |
'Vermillion City', | |
'Fuschia City', | |
'Special Region'}) | |
E = f({ | |
f({'Indigo Plateau', 'Viridian City'}), | |
f({'Pallet Town', 'Viridian City'}), | |
f({'Viridian City', 'Pewter City'}), | |
f({'Pewter City', 'Cerulean City'}), | |
f({'Cerulean City', 'Saffron City'}), | |
f({'Saffron City', 'Celadon City'}), | |
f({'Celadon City', 'Fuschia City'}), | |
f({'Fuschia City', 'Special Region'}), | |
f({'Fuschia City', 'Cinnabar Island'}), | |
f({'Vermillion City', 'Special Region'}), | |
f({'Cinnabar Island', 'Pallet Town'}), | |
f({'Saffron City', 'Lavender Town'}), | |
f({'Saffron City', 'Vermillion City'}), | |
f({'Lavender Town', 'Cerulean City'}), | |
f({'Lavender Town', 'Special Region'}) | |
}) | |
G = (V, E) | |
V = list(V) | |
E = list(E) | |
# print(E) | |
# define the problem and its variables and domains | |
problem = Problem() | |
# every town in Kanto can have either a Pokecenter either a Gym | |
for town in V: | |
varname = town.lower().replace(' ', '_') | |
problem.addVariable(varname, ['center', 'gym']) | |
# there can be no two gyms next to each other | |
for pair in list(E): | |
dest_i, dest_j = tuple(pair) | |
dest_i = dest_i.lower().replace(' ', '_') | |
dest_j = dest_j.lower().replace(' ', '_') | |
problem.addConstraint(lambda x, y: True if not x == y == 'gym' else False, [dest_i, dest_j]) | |
# print(dest_i, dest_j) | |
best_mis = [] | |
best_mis_size = 0 | |
best_mvc = [] | |
best_mvc_size = len(V) + 1 | |
# get CSP solution | |
solutions = problem.getSolutions() | |
# get COP solution | |
for solution in solutions: | |
values = list(solution.values()) | |
nb_gyms = values.count('gym') | |
nb_centers = values.count('center') | |
# MVC criterion | |
if nb_centers < best_mvc_size: | |
best_mvc = [solution] | |
best_mvc_size = nb_centers | |
elif nb_gyms == best_mvc_size: | |
best_mvc.append(solution) | |
# MIS criterion | |
if nb_gyms > best_mis_size: | |
best_mis = [solution] | |
best_mis_size = nb_gyms | |
elif nb_centers == best_mis_size: | |
best_mis.append(solution) | |
assert [i for i in best_mis if i not in best_mvc] == [] | |
print('succeedo!') | |
print() | |
for solution in best_mvc: | |
pp.pprint(solution) | |
print() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment