Programaci贸n de restricciones con python-constraint

    Introducci贸n

    Lo primero que tenemos que entender al tratar con la programaci贸n con 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 de restricciones es un ejemplo del paradigma de programaci贸n declarativa , a diferencia del paradigma imperativo habitual 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 se describe a menudo como una “forma de pensar” o “forma de programar”. Los ejemplos m谩s comunes incluyen programaci贸n procedimental (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 imperativos o declarativos.

    驴Cu谩l es la diferencia entre programaci贸n imperativa y declarativa?

    • La programaci贸n imperativa , en pocas palabras, se basa en que el desarrollador describe 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 el orden en que 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 dice a la computadora c贸mo darle los resultados que necesita? 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 “restricci贸n” para Python, eso no es lo que queremos), que tiene como objetivo llevar la idea de programaci贸n de restricciones a Python.

    Para instalar este m贸dulo, abra el terminal y ejecute:

    $ pip install python-constraint
    

    Conceptos b谩sicos del uso de restricci贸n de python

    Este es el esqueleto generalizado de los programas escritos usando este m贸dulo (Nota: usamos import constrainty no import python-constraint)

    • importar constraint
    • 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
    • revise las soluciones para encontrar las que necesitamos

    Como se mencion贸 anteriormente, la programaci贸n de 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
    Find all (x,y) where x 鈭 {1,2,3} and 0 <= y < 10, and x + y >= 5
    

    Si nos fijamos en esta frase, podemos ver una serie de condiciones (llam茅mosles limitaciones) que xy ytienen que cumplir.

    Por ejemplo, xest谩 “restringido” a los valores 1,2,3, ydebe ser menor que 10y su suma debe ser mayor o igual que 5. Esto se hace en unas pocas l铆neas de c贸digo y en unos minutos mediante la programaci贸n de restricciones.

    Mirando el problema anterior probablemente pensaste “驴Y qu茅? Puedo hacer esto con 2 ciclos for y media taza de caf茅 en Python en menos de 10 minutos”.

    Tiene 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:

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

    Salida:

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

    Repasemos este programa paso a paso. Ten铆amos dos variables xy y. Los hemos agregado a nuestro problema con sus respectivos rangos aceptables.

    Esas dos l铆neas significan lo siguiente:

    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 regresan Truesi una combinaci贸n de valores de variable es aceptable y Nonesi no lo es.

    En nuestro our_constraint()m茅todo, 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 .addConstraint()m茅todo es:

    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, obtuvimos 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 buscar solo combinaciones donde x /= y, agregar铆amos una restricci贸n incorporada antes de buscar las soluciones:

    problem.addConstraint(constraint.AllDifferentConstraint())
    

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

    Ejemplos de calentamiento

    Ejemplo B

    Aqu铆 hay un tipo de programaci贸n de restricci贸n de problemas que es divertido de usar, llamado rompecabezas criptogr谩fico . En la siguiente forma de rompecabezas criptogr谩fico, cada car谩cter representa un d铆gito diferente (los caracteres principales no pueden ser 0):

    TWO + TWO = FOUR
    

    Piense en c贸mo resolver铆a esto usando Python normal. De hecho, le animo a buscar la soluci贸n para este problema que utiliza programaci贸n imperativa.

    Tambi茅n deber铆a darte todo el conocimiento que necesitas para resolver el 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.

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

    Al ejecutar este c贸digo, nos saludan las posibles soluciones:

    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
    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 el que se imprime nuestro resultado no es necesariamente el mismo que el orden en el que agregamos las variables. Es decir, si el resultado es ( a,b,c,d,e) no sabemos si tenemos amonedas de 1 c茅ntimo, bde 3 c茅ntimos, etc.

    Entonces, deber铆amos imprimir expl铆citamente la variable y su valor. Una consecuencia de esto es que no podemos utilizar el built-in .ExactSumConstraint()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 debe multiplicarse), y no tenemos garant铆a de cu谩l de nuestras variables tendr谩 qu茅 peso.

    Es un error com煤n suponer que las ponderaciones se asignar谩n a las variables en el orden en que se agregaron, en su lugar usamos la forma de tres par谩metros de esta restricci贸n incorporada en el siguiente c贸digo:

    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谩:

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

    Los ejemplos B y D son casi id茅nticos cuando se usan restricciones, solo unas pocas variables hacia arriba y hacia abajo y restricciones m谩s detalladas. Eso es algo bueno de la programaci贸n de restricciones: buena escalabilidad, al menos cuando se trata de 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 cripto-taritm茅tica) se utilizan m谩s por diversi贸n y para una demostraci贸n sencilla de 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 emisoras 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 de restricciones puede tener usos en el mundo real.

    Ejemplos m谩s dif铆ciles

    Ejemplo E
    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 A1008 脳 2.5 脳 0.5208
    Chocolate B457 脳 2 脳 0.5166.8
    Chocolate C103 脳 2 脳 0.594
    Chocolate D253 脳 3 脳 0.573

    Ahora arremang茅monos y comencemos. No deber铆a ser demasiado dif铆cil si ha entendido los ejemplos anteriores.

    Primero averiguaremos cu谩nto de cada chocolate podemos tener si SOLAMENTE 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 aportar 37 como m谩ximo, y seg煤n el volumen podemos aportar 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 .

    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谩:

    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, por ejemplo weight_dictionary = {'A' : 100, 'B' : 45, 'C' : 10, 'D' : 25}, y acceder a valores de esa manera, en lugar de codificarlos en funciones. Sin embargo, en aras de la legibilidad, la longitud del c贸digo y el enfoque en las cosas m谩s importantes de este tutorial, prefiero codificar las funciones de restricci贸n en s铆 mismas.

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

    Ejemplo F

    Ahora, para algo m谩s divertido, hagamos un solucionador de sudoku (cl谩sico 9×9). Leeremos el rompecabezas de un archivo JSON y encontraremos todas las soluciones para ese rompecabezas en particular (asumiendo que el rompecabezas tiene una soluci贸n).

    Si olvid贸 las reglas para resolver sudoku:

    • Las celdas pueden tener valores del 1 al 9
    • Todas las celdas de la misma fila deben tener valores diferentes
    • Todas las celdas de la misma columna deben tener valores diferentes
    • Todas las celdas de un cuadrado de 3×3 (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.

    Usaremos un sistema en el que trataremos los n煤meros como nombres de variables (eso est谩 permitido) y pretendemos 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 una manera a la 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, por ejemplo (1, x) para la primera fila. Podemos recorrer f谩cilmente todas las filas y decir que todas las celdas deben contener valores diferentes. Lo mismo ocurre con las columnas. El resto se comprende m谩s f谩cilmente al mirar el c贸digo.

    Echemos un vistazo a un archivo JSON de ejemplo:

    [[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 - - - - - - - - -
    #   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):

    ==================
    |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 se asegura de que no toquemos los valores que ya est谩n en el rompecabezas.

    Si intent谩ramos ejecutar el c贸digo sin esa parte, el programa intentar铆a crear TODOS LOS PUZZLES DE SUDOKU IMAGINABLES. Que bien podr铆a ser un bucle sin fin.

    Conclusi贸n e inconvenientes

    Tan divertida y diferente como es la programaci贸n de restricciones, ciertamente tiene sus inconvenientes. Cada problema resuelto mediante la programaci贸n de restricciones se puede 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 python-constraint. Una nota muy importante a hacer 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 esto en la vida real. Una amiga m铆a, alguien que se enter贸 de la existencia de Python 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 que se resolviera el siguiente problema:

    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 pensar 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.

    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. Simplemente no agregamos ninguna restricci贸n y el programa gener贸 todas las combinaciones aceptables para nosotros. En su caso, la m铆nima diferencia en el tiempo de ejecuci贸n de este programa no importa ni remotamente tanto como qu茅 tan r谩pido fue escrito y qu茅 tan legible es.

    Una cosa m谩s a tener en cuenta es que python-constraintpuede hacer m谩s que simplemente probar si una combinaci贸n se ajusta a todas las restricciones sin pensar.

    Se implementan capacidades de retroceso (y retroceso recursivo), as铆 como tambi茅n un solucionador de problemas basado en la teor铆a de conflictos m铆nimos. Estos se pueden pasar como un argumento al .Problem()m茅todo, 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贸nDescripci贸n de la restricci贸nTodoDiferenteConstraintAllEqualConstraintMaxSumConstraintExactSumConstraintMinSumConstraintInSetConstraintNotInSetConstraintSomeInSetConstraintSomeNotInSetConstraint

    Hace que los valores de todas las variables dadas sean diferentes
    Hace que los valores de todas las variables dadas sean iguales
    Hace cumplir que los valores de las variables dadas suman una cantidad determinada
    Hace que los valores de las variables dadas sumen exactamente una cantidad determinada
    Restricci贸n que impone que los valores de las variables dadas sumen al menos una cantidad determinada
    Restricci贸n que impone que los valores de las variables dadas est茅n presentes en el conjunto dado
    Restricci贸n que impone que los valores de las variables dadas no est茅n presentes en el conjunto dado
    Restricci贸n que impone que al menos algunos de los valores de las variables dadas deben estar presentes en un conjunto dado
    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 (Me gusta ExactSumo MinSum), tenga cuidado de decir expl铆citamente el orden o las variables si es necesario, como hicimos en el Ejemplo E

    Conclusi贸n

    La programaci贸n de restricciones es sorprendente en lo que respecta a la legibilidad y la facilidad de desarrollo de 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.

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *