#constraint #satisfiability #csp #combinatorial #solving


A constraint solver supporting arithmetic constraints over integers

4 releases

Uses old Rust 2015

0.7.0 Dec 21, 2022
0.6.4 Jun 29, 2020
0.6.3 Jun 29, 2020
0.6.2 Jun 29, 2020

#429 in Math

50 downloads per month


5.5K SLoC

Constraint Programming Library

ptal on Travis CI

PCP is a library to model constraint satisfaction problems (CSPs) in the constraint programming paradigm. Constraint programming is a paradigm for expressing problems in terms of mathematical relations, called constraints, over variables (e.g. x > y). Constraints are an intuitive approach to naturally describe many real-world problems which initially emerged as a subfield of artificial intelligence and operational research. The flagship applications in constraint programming encompass scheduling, configuration and vehicles routing problems. Constraints are also applied to various other domains such as in music, biology and model checking.

It is a programming paradigm in its own right and being able to program in Rust is not sufficient to master the art of constraint programming. This is why I strongly recommend the class Basic Modeling for Discrete Optimization for those who wants to learn this paradigm. Meanwhile you can already look at the documentation for a running example.

PCP compiles on the stable Rust channel.


Existing libraries are an invaluable source of inspiration:

  • The csar Rust library by Sylvain Soliman helped me to get started.
  • And for a lot of reasons the following libraries are also interesting: GeCode, Choco, Minion,...

Most of this work has its roots in the following research works:

  • Guido Tack. Constraint Propagation - Models, Techniques, Implementation. Doctoral dissertation, Saarland University, 2009.
  • Tom Schrijvers, Peter Stuckey, and Philip Wadler. Monadic constraint programming. J. Funct. Program., 19(6):663–697, 2009.
  • Tom Schrijvers, Guido Tack, Pieter Wuille, Horst Samulowitz, and Peter J. Stuckey. Search combinators. Constraints, 18(2):269–305, 2013.
  • ...


~17K SLoC