Perhaps the most popular programming paradigm is imperative programming. But this is not the only kind of programming, functional and logical programming are widely known. Constraint Programming is not that popular. But it is a very powerful tool for solving combinatorial problems. Instead of implementing an algorithm that solves a problem, and then spending a lot of time debugging, refactoring and optimizing it, constraint programming allows you to simply describe the model in a special syntax, and a special program (solver) will find the solution for you (or tell if they are not). Impressive, isn't it? It seems to me that every programmer should be aware of this possibility.
Minizinc
Probably the most commonly used constraint programming tool (at least for educational purposes) is minizinc . It provides an IDE for declaring models and several built-in solvers for finding an answer. You can download the program from the official website .
Simple model in Minizinc
Let's consider an example of solving the model, let's start with a cryptoarithmetic problem. In this type of problem, all letters should be replaced with numbers with two conditions:
equality must hold
the same number must not correspond to different letters and vice versa.
For example, let's solve the following equation:
S E N D
+ M O R E
= M O N E Y
Model structure
minizinc , . - , , - , , , , , .
, , . , .
- :), .
. 8 (S, E, N, D, M, O, R, Y), , 0 9 (S M 1 9, ).
minizinc :
var 1..9: S;
var 0..9: E;
var 0..9: N;
var 0..9: D;
var 1..9: M;
var 0..9: O;
var 0..9: R;
var 0..9: Y;
, minizinc :
constraint 1000 * S + 100 * E + 10 * N + D
+ 1000 * M + 100 * O + 10 * R + E
== 10000 * M + 1000 * O + 100 * N + 10 * E + Y;
, . Minizinc alldifferent
, , include "alldifferent.mzn";
.
, , , , 3 : (satisfy), (minimize) (maximize) - , , :).
:
include "alldifferent.mzn";
var 1..9: S;
var 0..9: E;
var 0..9: N;
var 0..9: D;
var 1..9: M;
var 0..9: O;
var 0..9: R;
var 0..9: Y;
constraint 1000 * S + 100 * E + 10 * N + D
+ 1000 * M + 100 * O + 10 * R + E
= 10000 * M + 1000 * O + 100 * N + 10 * E + Y;
constraint alldifferent([S,E,N,D,M,O,R,Y]);
solve satisfy;
output [" ",show(S),show(E),show(N),show(D),"\n",
"+ ",show(M),show(O),show(R),show(E),"\n",
"= ",show(M),show(O),show(N),show(E),show(Y),"\n"];
Minizinc :
9567
+ 1085
= 10652
minizinc satisfy , , minizinc , , :).
Minizinc , constraint programming. , .
Python
minizinc-python , minizinc python, minizinc, , - . :
Spoiler
drop-down , - , , .
import minizinc
# Create a MiniZinc model
model = minizinc.Model()
model.add_string("""
var -100..100: x;
int: a; int: b; int: c;
constraint a*(x*x) + b*x = c;
solve satisfy;
""")
# Transform Model into a instance
gecode = minizinc.Solver.lookup("gecode")
inst = minizinc.Instance(gecode, model)
inst["a"] = 1
inst["b"] = 4
inst["c"] = 0
# Solve the instance
result = inst.solve(all_solutions=True)
for i in range(len(result)):
print("x = {}".format(result[i, "x"]))
, minizinc ( 4 ) string, IDE python .
Zython
, , Python?
, zython (miniZinc pYTHON). *.
Spoiler
* ,
* , Python. :)
zython, python 3.6+ minizinc $PATH
.
pip install zython
python
>>> import zython as zn
, . constraint programming zython.
Send More Money
— "Send More Money"
import zython as zn
class MoneyModel(zn.Model):
def __init__(self):
self.S = zn.var(range(1, 10))
self.E = zn.var(range(0, 10))
self.N = zn.var(range(0, 10))
self.D = zn.var(range(0, 10))
self.M = zn.var(range(1, 10))
self.O = zn.var(range(0, 10))
self.R = zn.var(range(0, 10))
self.Y = zn.var(range(0, 10))
self.constraints = [(self.S * 1000 + self.E * 100 + self.N * 10 + self.D +
self.M * 1000 + self.O * 100 + self.R * 10 + self.E ==
self.M * 10000 + self.O * 1000 + self.N * 100 + self.E * 10 + self.Y),
zn.alldifferent((self.S, self.E, self.N, self.D, self.M, self.O, self.R, self.Y))]
model = MoneyModel()
result = model.solve_satisfy()
print(" ", result["S"], result["E"], result["N"], result["D"])
print(" ", result["M"], result["O"], result["R"], result["E"])
print(result["M"], result["O"], result["N"], result["E"], result["Y"])
, .
, . , , , zython , , , , , python. , , . , zython Python , IDE . Zython .
. zn.Array
. , . .
import zython as zn
class MyModel(zn.Model):
def __init__(self):
self.a = zn.Array(zn.var(range(1, 10)), shape=(9, 9))
self.constraints = \
[zn.forall(range(9),
lambda i: zn.alldifferent(self.a[i])),
zn.forall(range(9),
lambda i: zn.alldifferent(self.a[:, i])),
zn.forall(range(3),
lambda i: zn.forall(range(3),
lambda j: zn.alldifferent(self.a[i * 3: i * 3 + 3, j * 3: j * 3 + 3]))),
]
model = MyModel()
result = model.solve_satisfy()
print(result["a"])
, minizinc, :
, , . :
import zython as zn
class TSP(zn.Model):
def __init__(self, distances):
self.distances = zn.Array(distances)
self.path = zn.Array(zn.var(range(len(distances))),
shape=len(distances))
self.cost = (self._cost(distances))
self.constraints = [zn.circuit(self.path)]
def _cost(self, distances):
return (zn.sum(range(1, len(distances)),
lambda i: self.distances[self.path[i - 1],
self.path[i]]) +
self.distances[self.path[len(distances) - 1],
self.path[0]])
distances = [[0, 6, 4, 5, 8],
[6, 0, 4, 7, 6],
[4, 4, 0, 3, 4],
[5, 7, 3, 0, 5],
[8, 6, 4, 5, 0]]
model = TSP(distances)
result = model.solve_minimize(model.cost)
print(result)
, , , .
Constraint programming - , , : , , , , , , , , .
Zython provides a way to express constraint programming model in pure python and solve this problem easily. You can see more examples in the documentation .
Constructive criticism, expressing one's opinion in the comments, bug reports, feature requests and PR are approved.
Good luck learning constrained programming.