Code repository for tutorial on constraint programming available on https://mareknarozniak.com/2020/06/22/constraint-programming/

diophantine.py

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']

kanto.py

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()