Skip to content

Instantly share code, notes, and snippets.

Last active April 17, 2023 00:32
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save marekyggdrasil/bb953f9bfd85430c1001c294ea7108ce to your computer and use it in GitHub Desktop.
Save marekyggdrasil/bb953f9bfd85430c1001c294ea7108ce to your computer and use it in GitHub Desktop.
Code repository for tutorial on constraint programming available on
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:
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:
# MIS criterion
if nb_gyms > best_mis_size:
best_mis = [solution]
best_mis_size = nb_gyms
elif nb_centers == best_mis_size:
assert [i for i in best_mis if i not in best_mvc] == []
for solution in best_mvc:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment