Вступление

Первое, что мы должны понять, имея дело с программированием в ограничениях, - это то, что образ мышления сильно отличается от нашего обычного мышления, когда мы садимся писать код.

Программирование с ограничениями - это пример парадигмы декларативного программирования в отличие от обычной императивной парадигмы, которую мы используем большую часть времени.

Что такое парадигма программирования?

Парадигма означает «пример» или «образец» чего-либо. Парадигма программирования часто описывается как «образ мышления» или «способ программирования». Наиболее распространенные примеры включают процедурное программирование (например, C), объектно-ориентированное программирование (например, Java) и функциональное программирование (например, Haskell).

Большинство парадигм программирования можно отнести к группе императивных или декларативных парадигм.

В чем разница между императивным и декларативным программированием?

• Проще говоря, императивное программирование основано на описании разработчиком решения / алгоритма достижения цели (некоего результата). Это происходит путем изменения состояния программы с помощью операторов присваивания при пошаговом выполнении инструкций. Поэтому очень важно, в каком порядке написаны инструкции.
• Декларативное программирование делает противоположное - мы не пишем шаги по достижению цели, мы описываем цель , и компьютер дает нам решение. Типичным примером, с которым вы должны быть знакомы, является SQL. Вы говорите компьютеру, как дать вам требуемый результат? Нет, вы описываете, что вам нужно - вам нужны значения из какого-то столбца, из какой-то таблицы, где выполняются какие-то условия.

Установка модуля ограничения Python

В этой статье мы будем работать с модулем под названием python-constraint (Примечание: для Python есть модуль под названием «constraint», это не то, что мы хотим), цель которого - передать идею программирования ограничений в Python.

Чтобы установить этот модуль, откройте терминал и запустите:

 $ pip install python-constraint 

Основы использования ограничения Python

Это обобщенный скелет программ, написанных с использованием этого модуля (Примечание: мы используем import constraint а не import python-constraint )

• constraint импорта
• определить переменную как нашу проблему
• добавить переменные и их соответствующие интервалы в нашу задачу
• добавить встроенные / настраиваемые ограничения к нашей проблеме
• получить решения
• пройтись по решениям, чтобы найти те, которые нам нужны

Как упоминалось ранее, программирование с ограничениями - это форма декларативного программирования. Порядок утверждений не имеет значения, если в конце все есть. Обычно он используется для решения таких задач:

Пример А

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

Если мы посмотрим на это предложение, то увидим несколько условий (назовем их ограничениями), которым должны соответствовать x и y

Например, x "ограничен" значениями 1,2,3 , y должен быть меньше 10 а их сумма должна быть больше или равна 5 . Это делается в несколько строк кода и за несколько минут с использованием программирования ограничений.

Глядя на проблему выше, вы, вероятно, подумали: «И что? Я могу сделать это с двумя циклами for и половиной чашки кофе на Python менее чем за 10 минут».

Вы абсолютно правы, хотя из этого примера мы можем получить представление о том, как выглядит программирование в ограничениях:

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

Выход:

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

Давайте пройдемся по этой программе шаг за шагом. У нас было две переменные, x и y . Мы добавили их к нашей проблеме с соответствующими допустимыми диапазонами.

Эти две строки означают следующее:

 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] 

Затем мы определяем наше настраиваемое ограничение (то есть x + y >= 5 ). Методы ограничения должны возвращать True если комбинация значений переменных приемлема, и None если нет.

В нашем our_constraint() мы говорим: «Единственная приемлемая ситуация

• когда x + y >= 5 , в противном случае не включайте эти значения (x,y) в окончательные решения».

После определения нашего ограничения мы должны добавить его к нашей проблеме. Структура метода .addConstraint() :

 addConstraint(which_constraint, list_of_variable_order) 

Примечание : в нашем случае не имеет значения, пишем ли мы [x,y] или [y,x] качестве второго параметра, но порядок в большинстве случаев имеет значение.

После этого мы получили решения с помощью problem.getSolutions() (возвращает список всех комбинаций значений переменных, которые удовлетворяют всем условиям), и мы перебираем их.

Примечание . Если, например, мы хотели получить только комбинации, в которых x /= y , мы бы добавили встроенное ограничение перед получением решений:

 problem.addConstraint(constraint.AllDifferentConstraint()) 

Вы можете найти список всех встроенных ограничений здесь . Это почти все, что вам нужно знать, чтобы выполнять любую задачу такого типа.

Примеры разминки

Пример Б

Вот тип проблемы программирования с ограничениями, который интересно использовать, он называется криптарифметическими головоломками . В следующей форме криптарифметических головоломок каждый символ представляет отдельную цифру (ведущие символы не могут быть 0):

 TWO + TWO = FOUR 

Подумайте, как бы вы решили эту проблему, используя обычный Python. Фактически, я рекомендую вам найти решение этой проблемы с использованием императивного программирования.

Это также должно дать вам все знания, необходимые для самостоятельного решения примера D.

Имейте в виду, что «T» и «F» не могут быть нулевыми, поскольку они являются ведущими символами, то есть первой цифрой в числе.

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

Запустив этот фрагмент кода, мы встречаемся с возможными решениями:

 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 

Пример 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. 

Примечание . Порядок, в котором печатается наш результат, не обязательно совпадает с порядком, в котором мы добавили переменные. То есть, если результат ( a,b,c,d,e ) мы не знаем , есть ли у нас 1 цент монеты, a b 3 центовых монет и т.д.

Поэтому мы должны явно распечатать переменную и ее значение. Одним из следствий этого является то, что мы не можем использовать встроенный .ExactSumConstraint() в его двухпараметрической форме ExactSumConstraint(50,[1,3,5,10,20]) .

Второй параметр здесь - это «вес» каждой переменной (сколько раз она должна быть умножена), и у нас нет гарантии, какая из наших переменных будет иметь какой вес.

Распространенная ошибка - предполагать, что веса будут присвоены переменным в том порядке, в котором они были добавлены, вместо этого мы используем трехпараметрическую форму этого встроенного ограничения в приведенном ниже коде:

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

Выполнение этого фрагмента кода даст:

 Total number of ways: 535 

Пример D

 CRASH + ERROR + REBOOT = HACKER 

Примеры B и D почти идентичны при использовании ограничений, только несколько переменных вверх и вниз и более подробные ограничения. В программировании с ограничениями есть одна хорошая черта - хорошая масштабируемость, по крайней мере, когда речь идет о времени, затраченном на кодирование. У этой загадки есть только одно решение: A = 3 B = 7 C = 8 E = 2 H = 6 K = 0 O = 1 R = 5 S = 9 T = 4.

Оба этих типа задач (особенно криптарифметические) используются больше для развлечения и для простой демонстрации того, как работает программирование в ограничениях, но есть определенные ситуации, в которых программирование в ограничениях имеет практическую ценность.

Мы можем рассчитать минимальное количество станций вещания, чтобы покрыть определенную территорию, или узнать, как настроить светофоры, чтобы поток трафика был оптимальным. В общих чертах - ограничения используются там, где существует множество возможных комбинаций.

Эти примеры слишком сложны для данной статьи, но служат для демонстрации того, что программирование с ограничениями может найти применение в реальном мире.

Более сложные примеры

Пример 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. 

Название шоколада Вес (г) Габаритные размеры (см) Сладость Стоимость ($)

Шоколад А 100 8 × 2,5 × 0,5 20 8 Шоколад B 45 7 × 2 × 0,5 16 6,8 Шоколадный C 10 3 × 2 × 0,5 9 4 Шоколад D 25 3 × 3 × 0,5 7 3

Теперь засучим рукава и приступим. Это не должно быть слишком сложно, если вы поняли предыдущие примеры.

Сначала мы выясним, сколько каждого шоколада мы можем съесть, если мы принесем ТОЛЬКО этот тип, чтобы мы могли иметь верхнюю границу наших интервалов. Например, для шоколада A, исходя из веса, мы можем принести максимум 30 батончиков, исходя из ценности, которую мы можем принести максимум 37, а в зависимости от объема мы можем принести 100.

Наименьшее из этих чисел - 30, и это максимальное количество шоколада А, которое мы можем принести. Те же шаги дают нам максимальное количество остальных, 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'])) 

Выполнение этого фрагмента кода даст:

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

Примечание . Мы можем хранить всю необходимую информацию для каждого типа шоколада в словаре, например, weight_dictionary = {'A' : 100, 'B' : 45, 'C' : 10, 'D' : 25} , и таким образом получать доступ к значениям. , вместо того, чтобы жестко закодировать их в functions. Однако для удобства чтения, длины кода и сосредоточения внимания на вещах, более важных для этого руководства, я предпочитаю жестко кодировать сами функции ограничения.

Примечание : вы, вероятно, заметили, что для вычисления этого результата потребовалось некоторое время, это недостаток программирования с ограничениями.

Пример F

А теперь повеселимся - сделаем решатель судоку (классический 9x9). Мы прочитаем головоломку из файла JSON и найдем все решения для этой конкретной головоломки (при условии, что у головоломки есть решение).

Если вы забыли правила решения судоку:

• Ячейки могут иметь значения от 1 до 9.
• Все ячейки в одной строке должны иметь разные значения.
• Все ячейки в одном столбце должны иметь разные значения.
• Все ячейки в квадрате 3x3 (всего девять) должны иметь разные значения.

Одна из проблем в этой программе - как мы храним значения? Мы не можем просто добавить матрицу в качестве переменной к нашей проблеме и заставить Python волшебным образом выяснить, что мы хотим.

Мы собираемся использовать систему, в которой будем обрабатывать числа как имена переменных (что разрешено) и делать вид, что у нас есть матрица. Индексы начинаются с (1,1) вместо обычного (0,0). Используя это, мы получим доступ к элементам доски привычным нам способом.

Затем нам нужно сделать простую часть сообщения Python, что все эти ячейки могут иметь значения от 1 до 9.

Затем отметим, что ячейки в одной строке имеют один и тот же первый индекс, например (1, x) для первой строки. Мы можем легко перебрать все строки и сказать, что все ячейки должны содержать разные значения. То же самое и со столбцами. Остальное легче понять, взглянув на код.

Давайте посмотрим на пример файла JSON:

 [[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.") 

Вывод (когда мы используем наш пример файла JSON в качестве ввода):

 ================== 
 |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 | 
 ================== 

Примечание . Очень легко упустить из виду ту часть кода, которая гарантирует, что мы не коснемся значений, уже содержащихся в головоломке.

Если бы мы попытались запустить код без этой части, программа попыталась бы выдать ВСЕ ВОСПРИНИМАЕМЫЕ ЗАГАДКИ СУДОКУ. Что с тем же успехом может быть бесконечным циклом.

Заключение и недостатки

Каким бы увлекательным и разнообразным ни было программирование с ограничениями, у него, безусловно, есть свои недостатки. Каждая проблема, решаемая с помощью программирования в ограничениях, может быть написана в императивном стиле с равной или (как в большинстве случаев) лучшей средой выполнения.

Вполне естественно, что разработчик понимает проблему лучше, чем может описать ее с помощью python-constraint . Очень важно отметить, что программирование с ограничениями в некоторых ситуациях может сэкономить часы и часы времени разработки в обмен на немного худшее время выполнения.

Недавно у меня был реальный пример этого. Моей подруге, которая узнала о существовании Python всего несколько месяцев назад, нужно было решить проблему для исследовательского проекта по физической химии, над которым она работала.

Этому другу нужно было решить следующую проблему:

 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. Ie 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).... 

Попробуйте подумать, как бы вы решили эту проблему, используя императивное программирование.

Я даже не мог придумать идею хорошего решения в императиве. По крайней мере, не за те 5 минут, которые мне потребовались, чтобы решить ее проблему в программировании с ограничениями, буквально в несколько строк кода.

 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) 

Вот и все. Мы просто не добавляли никаких ограничений, и программа сгенерировала для нас все приемлемые комбинации. В ее случае минимальная разница во времени выполнения этой программы не имеет такого большого значения, как то, насколько быстро она была написана и насколько она удобочитаема.

Еще одна вещь, которую следует отметить, заключается в том, что python-constraint может делать больше, чем просто бездумно проверять, соответствует ли комбинация всем ограничениям.

Реализованы возможности обратного отслеживания (и рекурсивного обратного отслеживания), а также средство решения проблем, основанное на теории минимума конфликтов. Их можно передать в качестве аргумента .Problem() , например .Problem(BacktrackingSolver) , остальное делается так же, как в примерах выше.

Список встроенных ограничений

Имя ограничения Описание ограничения

ВсеРазличныеОграничение Обеспечивает, чтобы значения всех заданных переменных были разными AllEqualConstraint Обеспечивает равенство значений всех заданных переменных MaxSumConstraint Обеспечивает, чтобы значения заданных переменных суммировались до заданной суммы ExactSumConstraint Обеспечивает, чтобы значения заданных переменных суммировались точно до заданной суммы MinSumConstraint Ограничение, требующее, чтобы значения заданных переменных суммировались, по крайней мере, с заданной суммой. InSetConstraint Ограничение, устанавливающее, что значения данных переменных присутствуют в данном наборе NotInSetConstraint Ограничение, устанавливающее, что значения данных переменных не присутствуют в данном наборе SomeInSetConstraint Ограничение, устанавливающее, что хотя бы некоторые из значений данных переменных должны присутствовать в данном наборе. SomeNotInSetConstraint Ограничение, устанавливающее, что по крайней мере некоторые из значений данных переменных не должны присутствовать в данном наборе.

При использовании ограничений, которые могут принимать список множителей в качестве параметра (например, ExactSum или MinSum ), постарайтесь явно указать порядок или переменные, если это необходимо, как мы это сделали в примере E

Заключение

Программирование с ограничениями великолепно с точки зрения удобочитаемости и простоты разработки определенных программ, но делает это за счет времени выполнения. Разработчик должен решить, что для него важнее для конкретной проблемы.