Programación de restricciones con python-constraint

Lo primero que tenemos que entender al tratar con la programación de restricciones es que la forma de pensar es muy diferente de nuestra forma habitual de pensar que...

Introducción

Lo primero que debemos entender al tratar con la programación de restricciones es que la forma de pensar es muy diferente de nuestra forma habitual de pensar cuando nos sentamos a escribir código.

La programación con restricciones es un ejemplo del paradigma de programación declarativo, a diferencia del paradigma habitual imperativo que usamos la mayor parte del tiempo.

¿Qué es un paradigma de programación?

Un paradigma significa "un ejemplo" o "un patrón" de algo. Un paradigma de programación a menudo se describe como una "forma de pensar" o "una forma de programar". Los ejemplos más comunes incluyen Programación de procedimientos (por ejemplo, C), Programación orientada a objetos (por ejemplo, Java) y Programación funcional (por ejemplo, Haskell).

La mayoría de los paradigmas de programación se pueden clasificar como miembros del grupo de paradigmas imperativo o declarativo.

¿Cuál es la diferencia entre programación imperativa y declarativa?

  • La programación imperativa, en pocas palabras, se basa en que el desarrollador describa la solución/algoritmo para lograr un objetivo (algún tipo de resultado). Esto sucede al cambiar el estado del programa a través de declaraciones de asignación, mientras se ejecutan las instrucciones paso a paso. Por lo tanto, hace una gran diferencia en qué orden se escriben las instrucciones.
  • La programación declarativa hace lo contrario: no escribimos los pasos sobre cómo lograr un objetivo, describimos el objetivo y la computadora nos da una solución. Un ejemplo común con el que debería estar familiarizado es SQL. ¿Le dices a la computadora cómo para darte los resultados que necesitas? No, usted describe lo que necesita: necesita los valores de alguna columna, de alguna tabla, donde se cumplen algunas condiciones.

Instalación del módulo de restricción de python

En este artículo trabajaremos con un módulo llamado python-constraint (Nota: hay un módulo llamado "constraint" para Python, eso no es lo que queremos), cuyo objetivo es traer la programación de restricciones idea a Python.

Para instalar este módulo, abra la terminal y ejecute:

1
$ pip install python-constraint

Conceptos básicos del uso de la restricción de python {#conceptos básicos del uso de la restricción de python}

Este es el esqueleto generalizado de los programas escritos usando este módulo (Nota: usamos restricción de importación y no restricción de importación de python)

  • importar restricción
  • definir una variable como nuestro problema
  • agregar variables y sus respectivos intervalos a nuestro problema
  • agregar restricciones integradas/personalizadas a nuestro problema
  • buscar las soluciones
  • revisar las soluciones para encontrar las que necesitamos

Como se mencionó anteriormente, la programación con restricciones es una forma de programación declarativa. El orden de las declaraciones no importa, siempre y cuando todo esté ahí al final. Por lo general, se usa para resolver problemas como este:

Ejemplo A
1
Find all (x,y) where x  {1,2,3} and 0 <= y < 10, and x + y >= 5

Si observamos esta oración, podemos ver varias condiciones (llamémoslas restricciones) que x e y deben cumplir.

Por ejemplo, x está "restringido" a los valores 1,2,3, y tiene que ser menor que 10 y su suma debe ser mayor o igual que 5. Esto se hace en unas pocas líneas de código y en unos pocos minutos utilizando la programación de restricciones.

Mirando el problema anterior, probablemente pensó "¿Y qué? Puedo hacer esto con 2 bucles for y media taza de café en Python en menos de 10 minutos".

Tienes toda la razón, aunque a través de este ejemplo podemos tener una idea de cómo se ve la programación de restricciones:

 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
import constraint

problem = constraint.Problem()

problem.addVariable('x', [1,2,3])
problem.addVariable('y', range(10))

def our_constraint(x, y):
    if x + y >= 5:
        return True

problem.addConstraint(our_constraint, ['x','y'])

solutions = problem.getSolutions()

# Easier way to print and see all solutions
# for solution in solutions:
#    print(solution)

# Prettier way to print and see all solutions
length = len(solutions)
print("(x,y) ∈ {", end="")
for index, solution in enumerate(solutions):
    if index == length - 1:
        print("({},{})".format(solution['x'], solution['y']), end="")
    else:
        print("({},{}),".format(solution['x'], solution['y']), end="")
print("}")

Producción:

1
(x,y)  {(3,9),(3,8),(3,7),(3,6),(3,5),(3,4),(3,3),(3,2),(2,9),(2,8),(2,7),(2,6),(2,5),(2,4),(2,3),(1,9),(1,8),(1,7),(1,6),(1,5),(1,4)}

Veamos este programa paso a paso. Teníamos dos variables, x e y. Los hemos agregado a nuestro problema con sus respectivos rangos aceptables.

Esas dos líneas significan lo siguiente:

1
I'm adding a variable x that can only have values [1,2,3], and a variable y that can only have values [0,1,2,..,9]

A continuación, definimos nuestra restricción personalizada (es decir, x + y >= 5). Se supone que los métodos de restricción devuelven Verdadero si una combinación de valores de variables es aceptable, y Ninguno si no lo es.

En nuestro método our_constraint(), decimos "La única situación aceptable es cuando x + y >= 5, de lo contrario, no incluya esos valores de (x,y) en las soluciones finales.\ "

Después de definir nuestra restricción, tenemos que agregarla a nuestro problema. La estructura del método .addConstraint() es:

1
addConstraint(which_constraint, list_of_variable_order)

Nota: en nuestro caso, no importa si escribimos [x,y] o [y,x] como nuestro segundo parámetro, pero el orden sí importa en la mayoría de los casos.

Después de eso, buscamos las soluciones con problem.getSolutions() (devuelve una lista de todas las combinaciones de valores de variables que satisfacen todas las condiciones) y las iteramos.

Nota: Si, por ejemplo, quisiéramos obtener solo combinaciones donde x /= y, agregaríamos una restricción integrada antes de obtener las soluciones:

1
problem.addConstraint(constraint.AllDifferentConstraint())

Puede encontrar la lista de todas las restricciones integradas aquí. Eso es casi todo lo que necesitas saber para poder hacer cualquier tarea de este tipo.

Ejemplos de calentamiento {#ejemplos de calentamiento}

Ejemplo B

Aquí hay un tipo de programación de restricción de problemas en la que es divertido usar, llamado rompecabezas criptoaritméticos. En la siguiente forma de acertijos criptoaritméticos, cada carácter representa un dígito diferente (los caracteres principales no pueden ser 0):

1
TWO + TWO = FOUR

Piensa en cómo resolverías esto usando Python normal. De hecho, te animo a que busques la solución a este problema que usa programación imperativa.

También debería darte todo el conocimiento que necesitas para resolver Ejemplo D por tu cuenta.

Tenga en cuenta que 'T' y 'F' no pueden ser cero ya que son los caracteres principales, es decir, el primer dígito de un número.

 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
import constraint

problem = constraint.Problem()

# We're using .addVariables() this time since we're adding
# multiple variables that have the same interval.
# Since Strings are arrays of characters we can write
# "TF" instead of ['T','F'].
problem.addVariables("TF", range(1, 10))
problem.addVariables("WOUR", range(10))

# Telling Python that we need TWO + TWO = FOUR
def sum_constraint(t, w, o, f, u, r):
    if 2*(t*100 + w*10 + o) == f*1000 + o*100 + u*10 + r:
        return True

# Adding our custom constraint. The
# order of variables is important!
problem.addConstraint(sum_constraint, "TWOFUR")

# All the characters must represent different digits,
# there's a built-in constraint for that
problem.addConstraint(constraint.AllDifferentConstraint())

solutions = problem.getSolutions()
print("Number of solutions found: {}\n".format(len(solutions)))

# .getSolutions() returns a dictionary
for s in solutions:
    print("T = {}, W = {}, O = {}, F = {}, U = {}, R = {}"
        .format(s['T'], s['W'], s['O'], s['F'], s['U'], s['R']))

Ejecutando este fragmento de código, somos recibidos con las posibles soluciones:

1
2
3
4
5
6
7
8
9
Number of solutions found: 7

T = 7, W = 6, O = 5, F = 1, U = 3, R = 0
T = 7, W = 3, O = 4, F = 1, U = 6, R = 8
T = 8, W = 6, O = 7, F = 1, U = 3, R = 4
T = 8, W = 4, O = 6, F = 1, U = 9, R = 2
T = 8, W = 3, O = 6, F = 1, U = 7, R = 2
T = 9, W = 2, O = 8, F = 1, U = 5, R = 6
T = 9, W = 3, O = 8, F = 1, U = 7, R = 6
Ejemplo C
1
2
3
You recently got a job as a cashier. You're trying to convince your friend that it's hard work, there are just SO many ways to give someone their change back! Your "friend" shakes his head, obviously not believing you. He says "It can't be that bad. How many ways can there POSSIBLY be to give someone their change back, for like 60 cents?".

Your response is, of course, to sit and quickly write a program that would prove your point. You have a decent amount of pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents), and a lot of kinda suspicious coins worth 3 cents each. Calculate in how many ways you can return change for 60 cents.

Nota: El orden en que se imprime nuestro resultado no es necesariamente el mismo que el orden en que agregamos las variables. Es decir, si el resultado es (a,b,c,d,e) no sabemos si tenemos a de monedas de 1 céntimo, b de monedas de 3 céntimos, etc.

Entonces deberíamos imprimir explícitamente la variable y su valor. Una consecuencia de esto es que no podemos usar la .ExactSumConstraint() integrada en su forma de dos parámetros, ExactSumConstraint(50,[1,3,5,10,20]).

El segundo parámetro aquí es el "peso" de cada variable (cuántas veces se debe multiplicar), y no tenemos ninguna garantía de cuál de nuestras variables tendrá qué peso.

Es un error común suponer que los pesos se asignarán a las variables en el orden en que se agregaron las variables; en su lugar, usamos la forma de tres parámetros de esta restricción integrada en el siguiente código:

 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
42
43
44
45
46
import constraint

problem = constraint.Problem()

# The maximum amount of each coin type can't be more than 60
# (coin_value*num_of_coints) <= 60

problem.addVariable("1 cent", range(61))
problem.addVariable("3 cent", range(21))
problem.addVariable("5 cent", range(13))
problem.addVariable("10 cent", range(7))
problem.addVariable("20 cent", range(4))

problem.addConstraint(
    constraint.ExactSumConstraint(60,[1,3,5,10,20]),
    ["1 cent", "3 cent", "5 cent","10 cent", "20 cent"]
)
# Where we explicitly give the order in which the weights should be allocated

# We could've used a custom constraint instead, BUT in this case the program will
# run slightly slower - this is because built-in functions are optimized and
# they find the solution more quickly
# def custom_constraint(a, b, c, d, e):
#     if a + 3*b + 5*c + 10*d + 20*e == 60:
#         return True
#     problem.addConstraint(o, ["1 cent", "3 cent", "5 cent","10 cent", "20 cent"])


# A function that prints out the amount of each coin
# in every acceptable combination
def print_solutions(solutions):
    for s in sols:
        print("---")
        print("""
        1 cent: {0:d}
        3 cent: {1:d}
        5 cent: {2:d}
        10 cent: {3:d}
        20 cent: {4:d}""".format(s["1 cent"], s["3 cent"], s["5 cent"], s["10 cent"], s["20 cent"]))
        # If we wanted to we could check whether the sum was really 60
        # print("Total:", s["1 cent"] + s["3 cent"]*3 + s["5 cent"]*5 + s["10 cent"]*10 + s["20 cent"]*20)
        # print("---")

solutions = problem.getSolutions()
#print_solutions(solutions)
print("Total number of ways: {}".format(len(solutions)))

Ejecutar este fragmento de código producirá:

1
Total number of ways: 535
Ejemplo D
1
CRASH + ERROR + REBOOT = HACKER

Los ejemplos B y D son casi idénticos cuando se usan restricciones, solo algunas variables hacia arriba y hacia abajo y restricciones más detalladas. Eso es algo bueno de la programación con restricciones: buena escalabilidad, al menos en lo que respecta al tiempo dedicado a la codificación. Solo hay una solución para este rompecabezas y es A=3 B=7 C=8 E=2 H=6 K=0 O=1 R=5 S=9 T=4.

Ambos tipos de tareas (especialmente la criptoaritmética) se usan más por diversión y para demostrar fácilmente cómo funciona la programación con restricciones, pero hay ciertas situaciones en las que la programación con restricciones tiene un valor práctico.

Podemos calcular el número mínimo de estaciones de radiodifusión para cubrir un área determinada, o averiguar cómo configurar los semáforos para que el flujo de tráfico sea óptimo. En términos generales, las restricciones se utilizan cuando hay muchas combinaciones posibles.

Estos ejemplos son demasiado complejos para el alcance de este artículo, pero sirven para mostrar que la programación con restricciones puede tener usos en el mundo real.

Ejemplos más difíciles {#ejemplos más difíciles}

Ejemplo E
1
2
3
4
5
You wish to pack chocolates for your mother. Luckily you work in a chocolate factory that has a lot of leftover chocolate. You have a few chocolate types at your disposal.

Your goal is to bring her the sweetest chocolate possible, that you can pack in your bag and sneak through security, and that wouldn't pass a certain net value for which you'd go to prison if you got caught.

Security most likely won't get suspicious if you bring less than 3kg. You can fit 1 dm^3 of chocolate in your bag. You won't go to jail if you steal less than $300 worth of chocolate.

Chocolate Nombre Peso (g) Dimensiones (cm) Dulzura Valor ($)


Chocolate A 100 8 × 2,5 × 0,5 20 8 Chocolate B 45 7 × 2 × 0,5 16 6,8 Chocolate C 10 3 × 2 × 0,5 9 4 Chocolate D 25 3 × 3 × 0,5 7 3

Ahora, arremanguémonos y comencemos. No debería ser demasiado difícil si has entendido los ejemplos anteriores.

Primero calcularemos cuánto de cada chocolate podemos tener si SÓLO trajimos ese tipo, para que podamos tener el límite superior de nuestros intervalos. Por ejemplo, para el Chocolate A, según el peso podemos traer como máximo 30 barras, según el valor podemos traer como máximo 37 y según el volumen podemos traer 100.

El menor de estos números es 30, y ese es el número máximo de Chocolate A que podemos traer. Los mismos pasos nos dan la cantidad máxima del resto, B -> 44, C -> 75, D -> 100.

 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
42
43
44
45
46
import constraint

problem = constraint.Problem()

problem.addVariable('A', range(31))
problem.addVariable('B', range(45))
problem.addVariable('C', range(76))
problem.addVariable('D', range(101))

# We have 3kg = 3,000g available
def weight_constraint(a, b, c, d):
    if (a*100 + b*45 + c*10 + d*25) <= 3000:
        return True

# We have 1dm^3 = 1,000cm^3 available
def volume_constraint(a, b, c, d):
    if (a*8*2.5*0.5 + b*6*2*0.5 * c*2*2*0.5 + d*3*3*0.5) <= 1000:
        return True

# We can't exceed $300
def value_constraint(a, b, c, d):
    if (a*8 + b*6.8 + c*4 + d*3) < 300:
        return True

problem.addConstraint(weight_constraint, "ABCD")
problem.addConstraint(volume_constraint, "ABCD")
problem.addConstraint(value_constraint, "ABCD")

maximum_sweetness = 0
solution_found = {}
solutions = problem.getSolutions()

for s in solutions:
    current_sweetness = s['A']*10 + s['B']*8 + s['C']*4.5 + s['D']*3.5
    if current_sweetness > maximum_sweetness:
        maximum_sweetness = current_sweetness
        solution_found = s

print("""
The maximum sweetness we can bring is: {}
We'll bring:
{} A Chocolates,
{} B Chocolates,
{} C Chocolates,
{} D Chocolates
""".format(maximum_sweetness, solution_found['A'], solution_found['B'], solution_found['C'], solution_found['D']))

Ejecutar este fragmento de código producirá:

1
2
3
4
5
6
The maximum sweetness we can bring is: 365.0
We'll bring:
27 A Chocolates,
2 B Chocolates,
16 C Chocolates,
2 D Chocolates

Nota: Podemos almacenar toda la información relevante para cada tipo de chocolate en un diccionario, p. weight_dictionary = {'A': 100, 'B': 45, 'C': 10, 'D': 25}, y acceder a los valores de esa manera, en lugar de codificarlos en funciones. Sin embargo, por el bien de la legibilidad, la longitud del código y el enfoque en cosas más importantes para este tutorial, prefiero codificar las funciones de restricción en sí.

Nota: Probablemente notó que tomó un tiempo calcular este resultado, esto es un retirarse de la programación de restricciones.

Ejemplo F

Ahora algo más divertido: hagamos un solucionador de sudoku (clásico 9x9). Vamos a leer el rompecabezas desde un archivo JSON y encontraremos todas las soluciones para ese rompecabezas en particular (asumiendo que el rompecabezas tiene un solución).

Si olvidaste las reglas para resolver sudoku:

  • Las celdas pueden tener valores 1 - 9
  • Todas las celdas en la misma fila deben tener valores diferentes
  • Todas las celdas en la misma columna deben tener valores diferentes
  • Todas las celdas en un cuadrado de 3x3 (nueve en total) deben tener valores diferentes

Uno de los problemas de este programa es: ¿cómo almacenamos los valores? No podemos simplemente agregar una matriz como variable a nuestro problema y hacer que Python descubra mágicamente lo que queremos.

Vamos a usar un sistema en el que trataremos los números como nombres de variables (eso está permitido) y fingiremos que tenemos una matriz. Los índices parten de (1,1) en lugar del habitual (0,0). Usando eso, accederemos a los elementos del tablero de la manera en que estamos acostumbrados.

A continuación, debemos hacer la parte fácil de decirle a Python que todas esas celdas pueden tener valores entre 1 y 9.

Luego notamos que las celdas en la misma fila tienen el mismo primer índice, p. (1,x) para la primera fila. Podemos iterar fácilmente a través de todas las filas y decir que todas las celdas deben contener valores diferentes. Lo mismo ocurre con las columnas. El resto se entiende más fácilmente al mirar el código.

Echemos un vistazo a un archivo JSON de ejemplo:

1
2
3
4
5
6
7
8
9
[[0, 9, 0, 7, 0, 0, 8, 6, 0],
 [0, 3, 1, 0, 0, 5, 0, 2, 0],
 [8, 0, 6, 0, 0, 0, 0, 0, 0],
 [0, 0, 7, 0, 5, 0, 0, 0, 6],
 [0, 0, 0, 3, 0, 7, 0, 0, 0],
 [5, 0, 0, 0, 1, 0, 7, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0, 9],
 [0, 2, 0, 6, 0, 0, 0, 5, 0],
 [0, 5, 4, 0, 0, 8, 0, 7, 0]]
 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# 1 - - - - - - - - -
# 2 - - - - - - - - -
# 3 - - - - - - - - -
# 4 - - - - - - - - -
# 5 - - - - - - - - -
# 6 - - - - - - - - -
# 7 - - - - - - - - -
# 8 - - - - - - - - -
# 9 - - - - - - - - -
#   1 2 3 4 5 6 7 8 9

import constraint
import json

problem = constraint.Problem()

# We're letting VARIABLES 11 through 99 have an interval of [1..9]
for i in range(1, 10):
    problem.addVariables(range(i * 10 + 1, i * 10 + 10), range(1, 10))

# We're adding the constraint that all values in a row must be different
# 11 through 19 must be different, 21 through 29 must be all different,...
for i in range(1, 10):
    problem.addConstraint(constraint.AllDifferentConstraint(), range(i * 10 + 1, i * 10 + 10))

# Also all values in a column must be different
# 11,21,31...91 must be different, also 12,22,32...92 must be different,...
for i in range(1, 10):
    problem.addConstraint(constraint.AllDifferentConstraint(), range(10 + i, 100 + i, 10))

# The last rule in a sudoku 9x9 puzzle is that those nine 3x3 squares must have all different values,
# we start off by noting that each square "starts" at row indices 1, 4, 7
for i in [1,4,7]:
    # Then we note that it's the same for columns, the squares start at indices 1, 4, 7 as well
    # basically one square starts at 11, the other at 14, another at 41, etc
    for j in [1,4,7]:
        square = [10*i+j,10*i+j+1,10*i+j+2,10*(i+1)+j,10*(i+1)+j+1,10*(i+1)+j+2,10*(i+2)+j,10*(i+2)+j+1,10*(i+2)+j+2]
        # As an example, for i = 1 and j = 1 (bottom left square), the cells 11,12,13,
        # 21,22,23, 31,32,33 have to be all different
        problem.addConstraint(constraint.AllDifferentConstraint(), square)

file_name = input("Enter the name of the .json file containing the sudoku puzzle: ")
try:
    f = open(file_name, "r")
    board = json.load(f)
    f.close()
except IOError:
    print ("Couldn't open file.")
    sys.exit()

# We're adding a constraint for each number on the board (0 is an "empty" cell),
# Since they're already solved, we don't need to solve them
for i in range(9):
    for j in range(9):
        if board[i][j] != 0:
            def c(variable_value, value_in_table = board[i][j]):
                if variable_value == value_in_table:
                    return True

            # Basically we're making sure that our program doesn't change the values already on the board
            # By telling it that the values NEED to equal the corresponding ones at the base board
            problem.addConstraint(c, [((i+1)*10 + (j+1))])

solutions = problem.getSolutions()

for s in solutions:
    print("==================")
    for i in range(1,10):
        print("|", end='')
        for j in range(1,10):
            if j%3 == 0:
                print(str(s[i*10+j])+" | ", end='')
            else:
                print(str(s[i*10+j]), end='')
        print("")
        if i%3 == 0 and i!=9:
            print("------------------")
    print("==================")

if len(solutions) == 0:
    print("No solutions found.")

Salida (cuando usamos nuestro archivo JSON de ejemplo como entrada):

 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
==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 345 |
------------------
|387 | 459 | 216 |
|612 | 387 | 594 |
|549 | 216 | 783 |
------------------
|768 | 524 | 139 |
|923 | 671 | 458 |
|154 | 938 | 672 |
==================
==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 345 |
------------------
|387 | 459 | 216 |
|612 | 387 | 594 |
|549 | 216 | 738 |
------------------
|763 | 524 | 189 |
|928 | 671 | 453 |
|154 | 938 | 672 |
==================
==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 543 |
------------------
|387 | 459 | 216 |
|612 | 387 | 495 |
|549 | 216 | 738 |
------------------
|763 | 524 | 189 |
|928 | 671 | 354 |
|154 | 938 | 672 |
==================

Nota: Es muy fácil pasar por alto la parte del código que asegura que no toquemos los valores que ya están en el rompecabezas.

Si tratáramos de ejecutar el código sin esa parte, el programa intentaría generar TODOS LOS ROMPECABEZAS DE SUDOKU IMAGINABLES. Que bien podría ser un bucle sin fin.

Conclusión e inconvenientes

Tan divertido y diferente como es la programación de restricciones, ciertamente tiene sus inconvenientes. Todos los problemas resueltos mediante la programación de restricciones se pueden escribir en estilo imperativo con un tiempo de ejecución igual o (como en la mayoría de los casos) mejor.

Es natural que el desarrollador comprenda el problema mejor de lo que puede describirlo a constricción de Python. Una nota muy importante a tener en cuenta es que la programación de restricciones puede, en algunas situaciones, ahorrar horas y horas de tiempo de desarrollo a cambio de un tiempo de ejecución ligeramente peor.

Recientemente tuve un ejemplo de la vida real de esto. Una amiga mía, alguien que se enteró de la existencia de Python solo unos meses antes, necesitaba resolver un problema para un proyecto de investigación de química física en el que estaba trabajando.

Ese amigo necesitaba resolver el siguiente problema:

1
2
3
4
5
6
Generate all combinations (that have a length equal to the number of keys) of values stored in a dictionary (the order of output doesn't matter). The dictionary is {String : List_of_Strings}. In such a way that every combination has exactly one value from the List_of_Strings of a key.

You don't know the number of keys in the dictionary in advance, nor do you know how long a List_of_String is, every List_of_String can be of different length. I.e. the dictionary is dynamically generated via user input.

Example input: dictionary = {"A" : [1,2], "B" -> [4], "C" -> [5,6,7], "D" -> [8,9]}
Example output: (1,4,5,8), (1,4,5,8), (1,4,6,8), (1,4,6,9), (1,4,7,8)....

Intente y piense cómo resolvería esto usando programación imperativa.

Ni siquiera se me ocurrió una idea de una buena solución en imperativo. Al menos no en los 5 minutos que me tomó resolver su problema en la programación de restricciones, literalmente en unas pocas líneas de código.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import constraint

# input example
generated_dictionary = {'A' : [1,2], 'B' : [4], 'C' : [5,6,7], 'D' : [8,9]}

problem = constraint.Problem()

for key, value in generated_dictionary.items():
    problem.addVariable(key, value)

solutions = problem.getSolutions()

for solution in solutions:
    print(solution)

Eso es todo. Simplemente no agregamos ninguna restricción y el programa generó todas las combinaciones aceptables para nosotros. En su caso, la diferencia mínima en el tiempo de ejecución de este programa no importa tanto como la rapidez con que se escribió y lo legible que es.

Una cosa más a tener en cuenta es que python-constraint puede hacer más que solo probar si una combinación se ajusta a todas las restricciones sin pensar.

Hay implementadas capacidades de retroceso (y retroceso recursivo), así como un solucionador de problemas basado en la teoría de conflictos mínimos. Estos se pueden pasar como un argumento al método .Problem(), por ejemplo .Problem(BacktrackingSolver), el resto se hace de la misma manera que en los ejemplos anteriores.

Lista de restricciones integradas

Nombre de la restricción Descripción de la restricción


AllDifferentConstraint Obliga a que los valores de todas las variables dadas sean diferentes AllEqualConstraint Obliga a que los valores de todas las variables dadas sean iguales MaxSumConstraint Obliga a que los valores de las variables dadas sumen una cantidad dada ExactSumConstraint Obliga a que los valores de las variables dadas sumen exactamente una cantidad dada MinSumConstraint Restricción que obliga a que los valores de las variables dadas sumen al menos una cantidad dada InSetConstraint Restricción que impone que los valores de las variables dadas están presentes en el conjunto dado NotInSetConstraint Restricción que impone que los valores de las variables dadas no están presentes en el conjunto dado SomeInSetConstraint Restricción que impone que al menos algunos de los valores de las variables dadas deben estar presentes en un conjunto dado SomeNotInSetConstraint Restricción que impone que al menos algunos de los valores de las variables dadas no deben estar presentes en un conjunto dado

Al usar restricciones que pueden tomar una lista de multiplicadores como parámetro (como ExactSum o MinSum), tenga cuidado de decir explícitamente el orden o las variables si es necesario, como hicimos en Ejemplo E

Conclusión

La programación con restricciones es increíble en lo que respecta a la legibilidad y la facilidad para desarrollar ciertos programas, pero lo hace a costa del tiempo de ejecución. Depende del desarrollador decidir qué es más importante para él/ella para un problema en particular. lar.

Licensed under CC BY-NC-SA 4.0