Constraint Programming with Python Constraint (2023)

introduction

The first thing we need to understand when looking at constraint programming is that the mindset is very different from our usual mindset when we sit down to write code.

Constraint programming is an example of this.declarativeProgramming paradigm, different from the usualImperativeparadigm we use most of the time.

What is a programming paradigm?

A paradigm means "an example" or "a pattern" of something. A programming paradigm is often referred to as a "mindset" or "way of programming". The most common examples, includingprocedural programming(z.B.C),Object Oriented Programming(e.g. Java) andfunctional programming(z. B. Haskell).

Most programming paradigms can be classified as members of the imperative or declarative paradigm group.

What is the difference between imperative and declarative programming?

• ImperativeIn short, programming relies on the developer describing the solution/algorithm to achieve a goal (some kind of result). It does this by changing the state of the program through assignment statements while the step statements are executing. So it makes a big difference the order in which the instructions are written.
• DeclarativeProgramming does the opposite: we don't write down the steps to reach a goal,We describe the objective, and the computer gives us a solution. A common example you might be familiar with is SQL. you tell the computerHe wasto give you the results you want? No, you describe what you need: you need values ​​from a column, a table in which some conditions are met.

Installing the Python Constraint Module

In this article we will work with a module calledPython Restriction(Note: there is a module called "constraint" for Python, we don't want that) which aims to bring the idea of ​​constraint programming to Python.

To install this module, open the terminal and run:

$ pip install Python constraint

Basics of using Python constraints

This is the generalized skeleton of programs written using this module (note: we useImport Restrictionand notImport Constraint from Python)

• to importrestriction
• define a variable as our problem
• Add variables and their respective ranges to our problem
• Add built-in/custom constraints to our problem
• look for the solutions
• Scroll through the solutions to find the ones we need

As mentioned above, constrained programming is a form of declarative programming. The order of the statements doesn't matter as long as everything is there at the end. It is usually used to solve problems like this:

Example A

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

Looking at this sentence, we can see several conditions (let's call them constraints).xjjyou have to find yourself

For example,xit is "restricted" to values.1,2,3,jmust be less than10and their sum must be greater than or equal to5🇧🇷 This is done in a few lines of code and in a few minutes using constraint programming.

When you saw the problem above, you probably thought, "So what? I can do this in Python in less than 10 minutes with 2 for loops and half a cup of coffee."

You're absolutely right, although this example gives us an idea of ​​what constraint programming looks like:

to importconstraint problem = constraint. problem() problem. addVariable('X', [1,2,3])problem.addVariable('y',offer(10))definitely our_restriction(x, y): ex + y >=5:give back Realproblem.addConstraint(our_constraint, ['X','y'])Solutions = problem.getSolutions()# Easiest way to print and view all solutions# for solution in solutions:# print (solution)# A nicer way to print and view all solutionsLongo =Len(Solutions)press("(x, y) ∈ {", fin="")through theindex, solutioninside enumerate(Solutions):eIndex == Length -1:press("({},{})".Format(Solution['X'], Solution['y']), fin ="")Most:press("({},{})".Format(Solution['X'], Solution['y']), fin ="")press("}")

Production:

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

Let's see this program step by step. We had two variablesxjj🇧🇷 We add them to our problem with their respective acceptable ranges.

These two lines mean the following:

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

We then define our custom constraint (i.e.x + y >= 5🇧🇷 Constraint methods must returnRealwhether a combination of variable values ​​is acceptable andNoneif not

In ourour_constraint()method, we say: "The only acceptable situation is whenx + y >= 5, otherwise do not delete these values(x,y)in the final solutions.

Now that we've defined our constraint, we need to add it to our problem. The structure of.addConstraint()method is:

addConstraint(what_constraint, list_of_order_variable)

To use: in our case it doesn't matter if we write[x,y]Ö[j,x]as our second parameter, but the order matters in most cases.

Then we look for solutionsproblema.getSolutions()(returns a list of all combinations of variable values ​​that satisfy all conditions) and iterates over them.

To use: For example, if we just want to get combinations wherex / = y, we would add a built-in constraint before getting the solutions:

problem.addConstraint(constraint.AllDifferentConstraint())

You can find the list of all built-in restrictionshere🇧🇷 That's almost all you need to know to be able to carry out a task of this type.

warm-up examples

Example B

Here's a fun type of constraint programming problem calledCryptoarithmetic puzzles🇧🇷 In the following form of cryptarithmetic puzzles, each character represents a different digit (leading characters cannot be 0):

TWO + TWO = FOUR

Think about how you would solve this using regular Python. In fact, I encourage you to use imperative programming to look for the solution to this problem.

It must also provide all the necessary knowledge to resolveExample Dalone

Note that 'T' and 'F' cannot be zero as they are the leading characters i.e. the first digit of a number.

to importconstraint problem = constraint. question ()# We use .addVariables() this time since we are adding# multiple variables that have the same scope.# Since strings are arrays of characters, we can write# "TF" statt ['T','F'].problema.addVariables("TF",offer(1,10))problem.addVariables("TO DIE",offer(10))# Tell Python we need TWO + TWO = FOURdefinitely constrain_sum(t, w, o, f, tu, r): e 2*(t*100+w*10+ o) == f*1000+o*100+du*10+r:give back Real# Add our custom constraint. The# The order of the variables matters!problem.addConstraint(sum_constraint,"TWO FOUR")# All characters must represent different digits,# There is a constraint built into thisproblem.addConstraint(constraint.AllDifferentConstraint())solutions = problem.getSolutions()press("Number of solutions found: {}\n".Format(Len(Solutions)))# .getSolutions() returns a dictionarythrough thesinsideSolutions:press("T = {}, W = {}, O = {}, F = {}, U = {}, R = {}".Format(s['T'], s['C'], s['Ö'], s['F'], s['Is it over there'], s['R']))

When we run this code snippet, we are greeted with possible solutions:

Anzahl der Lösungen: 7T = 7, W = 6, O = 5, F = 1, U = 3, R = 0T = 7, W = 3, O = 4, F = 1, U = 6, R = 8T = 8, W = 6, O = 7, F = 1, U = 3, R = 4T = 8, W = 4, O = 6, F = 1, U = 9, R = 2T = 8, W = 3, O = 6, F = 1, U = 7, R = 2T = 9, W = 2, O = 8, F = 1, U = 5, R = 6T = 9, W = 3, O = 8, F = 1, U = 7, R = 6

Example C

She recently got a job as a cashier. You're trying to convince your friend that it's hard work, there are MANY ways to get someone back! Your "friend" shakes his head, obviously not believing you. He says, "It can't be that bad. Your answer, of course, is to sit down and quickly write a program that proves your point. They have a decent amount of cents (1 cent), nickels (5 cents), nickels (10 cents) and quarters (25 cents) and lots of slightly suspect coins worth 3 cents each Find out how many ways you have to return the 60 cent change.

To use: The order in which our result is printed does not necessarily correspond to the order in which we add the variables. That is, if the result (a B C D e) We don't know if we haveone1 cent coins,b3 cent coins etc

Therefore, we must explicitly print the variable and its value. A consequence of this is that we cannot use the built-in.Exact Sum Constraint()in its two-parameter form,Constraint on exact sum (50, [1,3,5,10,20]).

The second parameter here is the "weight" of each variable (how many times to multiply it), and we are not guaranteed which of our variables has which weight.

It's a common mistake to assume that variables are weighted in the order they were added; Instead, we use the three-parameter form of this constraint, which is incorporated in the following code:

to importconstraint problem = constraint. question ()# The maximum amount of each type of currency cannot exceed 60# (coin_value*num_of_coins) <= 60problema.addVariable("1 cent",offer(61))problem.addVariable("3 cents",offer(21))problem.addVariable("5 cents",offer(13))problem.addVariable("10 Cent",offer(7))problem.addVariable("20 Cent",offer(4)) problem.addConstraint( constraint.ExactSumConstraint(60,[1,3,5,10,20]), ["1 cent","3 cents","5 cents","10 Cent","20 Cent"])# where we explicitly specify the order in which to assign the weights# We could have used a custom constraint BUT in this case the program# Runs a little slower: this is due to built-in functions being tweaked and optimized# find the solution faster# def custom_constraint(a, b, c, d, e):# si a + 3*b + 5*c + 10*d + 20*e == 60:# returns true# problem.addConstraint(o, ["1 Cent", "3 Cent", "5 Cent", "10 Cent", "20 Cent"])# A function that prints the value of each coin# in all acceptable combinationsdefinitely printing solutions(solutions): through thesinsidesolas:press("---")press(""" 1 cent: {0:d} 3 cents: {1:d} 5 cents: {2:d} 10 cents: {3:d} 20 cents: {4:d}""".Format(s["1 cent"], s["3 cents"], s["5 cents"], s["10 Cent"], s["20 Cent"]))# If we wanted to, we could check if the total is really 60 # print("Total:", s["1 Cent"] + s["3 Cent"]*3 + s["5 Cent"]*5 + s["10 Cent"]*10 + s["20 Cent"]*20) # Press("---")Solutions = problem.getSolutions()#print_solutions(solutions)press("Total forms: {}".Format(Len(Solutions)))

Running this piece of code produces the following:

Total titles: 535

Example D

FAIL + ERROR + RESET = HACKER

Examples B and D are nearly identical in using constraints, just a few up and down variables and more detailed constraints. This is good in constrained programming: good scalability, at least as far as time spent programming is concerned. There is only one solution to this puzzle, which is A=3 B=7 C=8 E=2 H=6 K=0 O=1 R=5 S=9 T=4.

Both types of problems (especially cryptarithmetic) are used more for fun and to simply demonstrate how constrained programming works, but there are certain situations where constrained programming has practical value.

We can calculate the minimum number of transmitters to cover a given area or figure out how to configure traffic lights to optimize traffic flow. In general, constraints are used when there are many possible combinations.

These examples are too complex for the scope of this article, but they serve to show that constrained programming can be used in the real world.

more difficult examples

Example E

You want to wrap chocolates for your mother. Luckily you work in a chocolate factory that has a lot of chocolate left over. You have some types of chocolate at your disposal. Your goal is to get her the cutest chocolate she can fit in her bag and sneak it through security that doesn't exceed a certain net worth that she would go to jail for if caught. Security will probably not be suspicious if you carry less than 3 kg. You can put 1 dm^3 of chocolate in your bag. You won't go to jail if you steal less than $300 worth of chocolate.

Now let's roll up our sleeves and get started. It shouldn't be too difficult once you understand the examples above.

First, let's calculate how much of each chocolate we can eat if we bring ONLY that kind, to get the upper limit of our ranges. For example, for chocolate A we can bring a maximum of 30 bars depending on the weight, a maximum of 37 depending on the value and 100 bars depending on the volume.

The smallest of these numbers is 30, and that's the maximum number of A chocolates we can bring. The same steps give us the maximum amount of remainder,B -> 44, C -> 75, D -> 100.

to importconstraint problem = constraint. problem() problem. addVariable('ONE',offer(31))problem.addVariable('B',offer(45))problem.addVariable('C',offer(76))problem.addVariable('D',offer(101))# We have 3kg = 3000g availabledefinitely Weight Limit(A B C D): e(one*100+b*45+c*10+ again*25) <=3000:give back Real# We have 1dm^3 = 1000cm^3 availabledefinitely volume_restriction(A B C D): e(one*8*2.5*0,5+b*6*2*0,5*C*2*2*0,5+ again*3*3*0,5) <=1000:give back Real# We cannot exceed $300definitely constraint value(A B C D): e(one*8+b*6.8+c*4+ again*3) <300:give back Realproblem.addConstraint(weight_constraint,"A B C D")problem.addConstraint(constraint_volume,"A B C D")problem.addConstraint(constraint_value,"A B C D") maximum_cute =0solution_found = {}solutions = problem.getSolutions()through thesinsideSolutions: sweet_current = s['ONE']*10+s['B']*8+s['C']*4.5+s['D']*3.5 ecurrent_sweetness > maximum_sweetness: maximum_sweetness = current_sweet_solution_found = spress("""The maximum sweetness we can bring is: {}We bring:{}A chocolates,{}B chocolates,{}C chocolates,{}D chocolates""".Format(maximum_sweetness, solution_found['ONE'], Solution found['B'], Solution found['C'], Solution found['D']))

Running this piece of code produces the following:

The maximum sweetness we can bring is: 365.0. We bring: 27 B chocolates, 2 B chocolates, 16 C chocolates, 2 D chocolates

To use: We can store all relevant information in a dictionary for each type of chocolate, eg.dictionary_weight = { 'A': 100, 'B': 45, 'C': 10, 'D': 25};, and access the values ​​that way rather than hardcoding them in functions. However, for readability, code length, and focus on more important things for this tutorial, I prefer to code the constraint functions myself.

To use: You've probably noticed that it took a while to calculate this result, that's ato throwconstraint programming.

For example F

Now something more fun: let's make a Sudoku solver (classic 9x9). GoodRead the puzzle from a JSON fileand find all the solutions to that particular puzzle (assuming the puzzle has a solution).

If you forgot the rules for solving Sudoku:

• Cells can have values ​​from 1 to 9
• All cells in the same row must have different values
• All cells in the same column must have different values
• All cells in a 3x3 square (nine total) must have different values

One of the problems with this program is: how do we store the values? We can't just add an array as a variable to our problem and let Python magically figure out what we want.

Let's use a system where we treat numbers as variable names (this is allowed) and pretend we have an array. Indexes start at (1,1) instead of the usual (0,0). With that, we access the elements of the board as usual.

Next we need to tell Python the easy part, that all these cells can have values ​​between 1 and 9.

Then we find that the cells in the same row have the same first index, for example (1,x) for the first row. We can just go through all the rows and say that all the cells must contain different values. The same applies to columns. The rest is easier to understand by looking at the code.

Let's look at an example JSON file:

[[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 9to importrestrictionto importjsonproblem = Constraint.Problem()# We leave the VARIABLES from 11 to 99 an interval of [1..9]through theEUinside offer(1,10): problema.addVariables(offer(EU *10+1, EU *10+10),offer(1,10))# Added restriction that all values ​​in a series must be different#11 to 19 must be different, 21 to 29 must all be different,...through theEUinside offer(1,10): problem.addConstraint(constraint.AllDifferentConstraint(),offer(EU *10+1, EU *10+10))# All values ​​in a column must also be different# 11,21,31...91 must be different, also 12,22,32...92 must be different,...through theEUinside offer(1,10): problem.addConstraint(constraint.AllDifferentConstraint(),offer(10+ e,100+ e,10))# The final rule in a 9x9 Sudoku game is that these nine 3x3 squares must have different values,# Let's start by noting that each square "starts" at row indices 1, 4, 7.through theEUinside[1,4,7]:# Then we notice that it's the same for columns, squares also start at indices 1, 4, 7 # Basically, one square starts at 11, another at 14, another at 41, etc. through thejinside[1,4,7]: Square = [10*i+j,10*i+j+1,10*i+j+2,10*(e+1)+j,10*(e+1)+j+1,10*(e+1)+j+2,10*(e+2)+j,10*(e+2)+j+1,10*(e+2)+j+2]# As an example for i = 1 and j = 1 (lower left corner), cells 11,12,13, #21,22,23,31,32,33 must all be differentproblem.addConstraint(constraint.AllDifferentConstraint(), quadrado)file_name =Prohibited("Enter the name of the .json file that contains sudoku: ")Try: f =Open(file name,"r") tablero = json.load(f) f.close()exceptI/O error:press("The file could not be opened.") sys.exit()# Added a constraint for each number in the frame (0 is an "empty" cell)# Since they are already resolved, we don't need to resolve themthrough theEUinside offer(9):through thejinside offer(9):eBrett[i][j] !=0:definitely C(variable_value, table_value = plate[i][j]): evariable value == value_in_table:give back Real # Basically, we make sure our program doesn't change the values ​​that are already in the frame # Tell it the values ​​MUST be the same as on the motherboardproblema.addConstraint(c, [((i+1)*10+ (j+1))])solutions = problem.getSolutions()through thesinsideSolutions:press("==================")through theEUinside offer(1,10):press("|", fin='')through thejinside offer(1,10):ej%3==0:press(turn on(e*10+j])+" | ", fin='')Most:press(turn on(e*10+j]), final='')press("")eEU%3==0 je!=9:press("------------------")press("==================")e Len(Solutions) ==0:press("No solution found.")

Output (if we use our sample JSON file as input):

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

To use: It's too easy to miss the part of the code that makes sure we don't touch values ​​that are already in the puzzle.

If we tried to run the code without this part, the program would try to generate EVERY SUDOKU PUZZLE IMaginable. It can also be an infinite loop.

Conclusion and disadvantages

As fun and different as constraint programming is, it certainly has its downsides.AllThe problem solved by constraint programming can be written in imperative style with the same or (in most cases) better running time.

It is natural for the developer to understand the problem better than he can describe it to you.Python Restriction🇧🇷 A very important note to keep in mind is that, in some situations, constraint programming can save hours and hours of development in exchange for slightly worse execution time.

I recently had a real example of this. A friend of mine who discovered Python just a few months ago needed to solve a problem for a physicochemical research project she was working on.

This friend had to solve the following problem:

Generate all combinations (of length equal to the number of keys) of values ​​stored in a dictionary (output order does not matter). The dictionary is {String : List_of_Strings}. So that each combination has exactly one List_of_Strings value of a key. You don't know in advance the number of keys in the dictionary, nor how long a List_of_String is, each List_of_String can have a different length. Namely. The dictionary is dynamically generated by user input. Example entry: 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) ....

Try and think how you would solve this using imperative programming.

I couldn't even think of oneIdeaabsolutely necessary for a good solution. At least not in the 5 minutes it took me to literally solve your constraint programming problem.some linesby code

to importrestriction# Input exampledictionary_generated = {'ONE': [1,2],'B': [4],'C': [5,6,7],'D': [8,9]}problema = Constraint.Problem()through thekey valueinsidegenerate_dictionary.items(): problem.addVariable(chave, valor)solutions = problem.getSolutions()through thesolutioninsideSolutions:press(Solution)

That is all. We just didn't add any restrictions and the program generated all acceptable combinations for us. In your case, the small difference in running time of this program doesn't matter so much how fast it was written and how readable it is.

Another thing to note is thatPython RestrictionYou can do more than just mindlessly test whether a combination meets all the constraints.

Backtracking (and recursive backtracking) functions are implemented, as well as a problem solver based on least conflict theory. These can be passed as an argument to the.Problem()method for example.Problema (Backspace-Resolve), the rest is done in the same way as in the previous examples.

Built-in restrictions list

When using constraints that can take a list of multipliers as parameters (for exampleExaggeratedÖherr sum) be sure to explicitly specify the order or variables if needed like we did inExample E

Conclusion

Limited programming is awesome when it comes to readability and ease of development of certain programs, but at the cost of runtime. It is up to the developer to decide what is most important to him for a given problem.