The million queens problem

In my last post I mentioned part of my family (kids, wife and even grand mother) to illustrate some Decision Optimization concepts. In this one I want to mention the other part of my family who introduced me to Decision Optimization: my parents.

Logic Programming

Decision Optimization is based on two quite different types of techniques: Mathematical Programming on one side, coming from the Operation Research area, and Constraint Programming on the other side, coming from the Artificial Intelligence research area. The first one was mostly developed in the US while the second one was mostly developed in Europe, and had a strong community in France.

This started with Logic Programming, and languages like Prolog, which was born around the same years than me (1972), in the same area than me (France). While there are different types of applications for Logic Programming in the area of Artificial Intelligence, such as the monkey-banana problem (see some video about Prolog resolution of this problem), one particular field of investigation has been about solving what we would commonly call puzzles, but which are academically known as combinatorial problems.

Combinatorial Problems and Constraint Programming

A combinatorial problem is a problem where different unknowns can take different values (integer values, colors, indices, etc) and where a solution is a valid combination of these values for these variables.

One example is the map coloring problem: how to color each country in a map of Europe without using the same color for two adjacent countries. This applies to any map and in fact can be generalized as one particular case of Graph Coloring problem. Note that only very recently it is has been proven that you can always color a map with 4 colors.

Another very famous example is the Einstein puzzle (also known as the Zebra problem). Prolog programming was a way to solve that kind of problems, and this is where the other part of my family enters into play. My mother and my father were working on this at the time. We had one of first Apple II computers in France with some Prolog version on which I have seen how this type of problem can be solved with that type of techniques. See for example this example of program.

At some point, part of Logic Programming evolved and a new field emerged known as  Constraint Programming (CP) with a more important focus on domains propagations among logical variables and backtracking.

The 8 queens problem

One typical example which has been used to explain CP and to illustrate how it works was the 8 queens problem. Wikipedia definition of the problem is to place “eight chess queens on an 8×8 chessboard so that no two queens threaten each other.”

The CP approach to model the problem is to use a variable for each queen. Each queen will be placed on a different column of the board. The variable has 8 possible values representing the possible position of the queen in its respective column. By design of the variables, queens are not threatening on the same column. One “alldifferent” constraint ensure all variables should have different value to prevent queens to threaten on the same row.  Similar “alldifferent” constraints are used to avoid queens to threaten on diagonals. You can see here how we would model this problem using Python and the IBM docplex API.

The resolution of this problem is also illustrative of how CP works. Some value is “tried” for the first variable, and constraints are propagated. For example, if queen 1 is placed on row 1, then the propagation of the alldifferent constraint results in value 1 being removed from all domains of other queens. After propagation of all constraints, either, i. all variables ends with a unique possible value, and we have a solution to the problem, ii. some variable has no more possible value in its domain, this is a failure and we backtrack to the last “choice point” and “try” another value, or iii. some variable still have different possible values in its domain and we need to do additional choices.

So the solution search is a tree search with intermediate nodes corresponding to choice points among different possible values in some variable domain, and leaves corresponding to either solutions or failures. At each node, the last choice leads to constraints propagation. And at each failure we backtrack to the last choice point with non explored alternatives.

Then the ability to find solution quickly highly depends on the part of the search-tree that is explicitly explored, which highly depends on how “strongly” constraints propagate. This is where most of CP academic literature is focusing, and in particular the alldifferent constraints has been a good example of possible improvements (see this survey).

You can see here a much more complete course on CP.

From 8 to 1 000 000

You might have noticed that this old 8 queens problem is similar in some way to the sudoku problem which is the new typical CP illustrative example. But you might still wonder how solving this type of problem can be useful with respect to real life problems. In practice, these academical examples are representative of real life combinatorial problems such as scheduling tasks with competing resources requirements. This is why it is important to solve such small problems efficiently and be able to solve bigger instances of these problems.

You can indeed grow the 8 queens problems to a N queens problems. This 1991 academic publication, from Jacqueline Chabrier, Jean-Jacques Chabrier and Fran?ois Trousset describes how the 1 million queens problem could be solved for the first time. Now with Constraint Programming techniques included in the IBM CPLEX engine, we solve scheduling problems with huge number of activities and resources. See CPLEX CP Optimizer.