Constraint Programming is a *valuable* tool for solving different types of optimization problems (especially industrial programming problems). So today we’re going to introduce some basic definitions and the conceptual model behind it.

Constraint** optimization, or**constraint scheduling (CP), is the name given to identifying feasible solutions from a very large set of candidates, where the problem can be modeled in terms of arbitrary constraints. CP is based on feasibility rather than optimization and focuses on constraints or variable domains instead of the target function.

We will dissect the solution of the “4 Queens Problem” example, which is to place four queens on a 4 x 4 chessboard so that they cannot be captured from each other, to demonstrate the concepts behind CP. We start by translating the problem into a mathematical model with variables and constraints. The *solver then* uses *Backtracking to*reach the solution.

Variables **represent** some decisions. They can contain any value included in their range or domain. In our problem we create variables for each box on the board. Each variable takes the value 1 if a queen is present in the given box, otherwise it is 0.

Constraints prevent variables from taking arbitrary values. You cannot place two queens in the same row, same column, or diagonal.

**Propagation –**Variables can have different values, but the *solver* must delete some of those values to maintain all variables supported by the model.

**Backtracking**– Occasionally, the *solver is locked because it* tries to assign some values to some variables that are simply not possible (or desirable) because they do not respect constraints. You need to rethink your previous choices and test other values. Backtracking also occurs when the solver *finds * a solution, but it is interested in continuing the search to find other solutions.

Now let’s see how the CP *solver* comes to the solution for our problem:

1. You could start by placing the Queen in the upper left corner, so the corresponding variable is assigned to 1. Propagating constraints would cause the other variables in the top row, left column, and main diagonal to be assigned to 0, because no other Queen can already occupy these positions.

2. After a few steps, the *solver* may encounter the following situation:

It is not possible to place the Queen in the third column without violating the restrictions. Therefore, you must go back and review your previous decision to place the Queen in the third row of the second column. That’s *Backtracking.*

3. After several propagation and resolution cycles, the *solver hopes* to reach the solution:

Now let’s see how we would program this **solution using ConstraintSolver** from the Google **OR-Tools **library:

- var n = 4; var solver = new Solver(“N-Queens”);
*// // Decision variables. q[i] row in i-th column where we place the queen // var q = solver.MakeIntVarArray(n, 0, n – 1, “q”); // // Constraints // solver.Add(q.AllDifferent()); var q1 = new IntVar[n]; var q2 = new IntVar[n]; //The following sets the constraint that no two queens can be on the same diagonal. for (int i = 0; i < n; i++) { q1[i] = (q[i] + i).Var(); q2[i] = (q[i] – i).Var(); } solver.Add(q1.AllDifferent()); solver.Add(q2.AllDifferent()); // // Search // var db = solver.MakePhase(q, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE); solver.NewSearch(db); var s = 1; while (solver.NextSolution()) { Console.WriteLine($”Solution {s++}: “); for (int i = 0; i < n; i++) { Console.Write(“{0} “, q[i].Value()); } Console.WriteLine(string.Empty); } solver.EndSearch();*

In this example, 4 variables, one per row, have been used, which can take values between 0 and 3, indicating the column where the Queen would be placed.

And the result is:

**Solution**1: 1 3 0 2

**Solution**2: 2 0 3 1

Basically, that’s all. Happy programming!