Constraint Programming
What is constraint programming?
Constraint programming is one model approach for solving combinatorial problems. A combinatorial problem is any problem that can be solved by finding an optimal solution from a set of finite and discrete quantities. The goal of constraint programming is to create a set of rules that limit the number of combinations we have to test, thereby increasing the speed with which we can solve our problem. Unlike permutations, combinations don’t need to consider the order of the values being processed.
Okay, so what is Combinatorics?
Combinatorics is a subfield of mathematics and programming that focuses on finding optimal solutions to problems by utilizing the constraint programming paradigm. In our everyday lives, we participate in the study of combinatorics — without ever realizing it — when we deal with scheduling appointments or making plans to meet up with friends somewhere. Casinos use combinatorics to calculate payouts from Roulette, craps, and poker. In computer science, a few applications of combinatorics are algorithmic efficiency, block design (cryptography), and Big O Time Complexity.
What all of these things have in common is that they take place in time, they take up space, and the number of possible solutions is constrained to a pool of finite options. Knowing our constraints can help us find the optimal solution in the shortest possible amount of time.
Time, Space, Constraints, Optimization
Constraint programming isn’t a good strategy for every problem, but it is often highly effective when we are confronted with a problem for which we can identify and describe our constraints.
The n-Rooks and n-Queens problems are both good examples of problems that can be efficiently solved by identifying and describing constraints.
Don’t Cares
On an n * n chessboard, where n is the number of rooks, how many pieces can be placed without attacking any other pieces?
Rather than iterating through the space of the entire chessboard and finding every possible permutation of rooks placements, we can save time by applying constraints to immediately rule out possible placements that we don’t care about.
For N-Rooks, what are our constraints?
1. Only one rook per row.
2. Only one rook per column.
For a fairly straightforward problem like the 4-Rooks example in my doodle (at left), we can see that our constraints make it so that there are only two possible sets of solutions:
The solution illustrated and its mirror image.
That means any other combinations of options can be immediately discarded as don’t cares, which saves time. The constraints identified above in turn describe an overarching rule that allows the n-Rooks problem to be broken down to its base components:
If we start with one rook on a 1*1 chessboard, we can only add each subsequent rook to its own column and row.
I won’t get into the code in this blog, but the above description allows n-Rooks to be solved with a simplistic recursive algorithm. Although somewhat more complex, due to the inclusion of diagonal conflicts, n-Queens can also be solved by clearly identifying and describing its constraints.
Why you should try Constraint Programming
Tl; dr: effectively applied constraints allow us to streamline our code by reducing complexity.
