Home

February 21, 2019

N Queens with a Twist and a Constraint Solver

The n queens problem is a well-known challenge requiring the placement of n queens on an n-by-n chessboard such that no two queens can attack each other. For n = 8, one possible solution is:

Recently I was posed a modified version of this problem: in addition to the original requirements, it was also required that no three queens appear on the same line at any angle. In other words, no three queens are allowed to be collinear. Under this additional criterion, the solution above would be inadmissible, as queens C4, D6, and E8 all lie on the same line.

When I first solved this, I rolled my own code but was unsatisfied with not knowing for sure whether I was completely right. Thus I turned to the land of constraint solvers. In the end I discovered I had made a small mistake in my code that counted some invalid board configurations as valid. With the benefit of hindsight, this post will go in reverse: we’ll first solve this with the CP-SAT solver in Google’s OR Tools, then roll some code using a modified version of the classic backtracking algorithm, ensuring that both approaches agree with each other (at least for all values of n up to 15).

Constraint Solving

The n queens problem is one of the examples outlined by the developers of Google OR Tools; you can read about it here. On that page they walk through a solution for the vanilla version of the challenge using Python bindings to the solver. In particular, they explain how to encode as constraints the requirements that no two queens occupy the same row, column, or diagonal on the board.

If their explanations make clear sense to you, we can proceed to add our problem’s particular twist into the mix. We know that, given the vanilla constraints, we will never place more than two queens in the same row or column. Thus, as we move across rows or columns, we will be expanding a “window” containing one additional queen for every additional row or column. Due to the symmetry of the board and of these constraints, it should be evident that we could choose either rows or columns to work with going forward; I’m going to choose rows and describe how to develop the constraint we must add to the solver.

For any board of dimension n = 3 or more, we know that row 1 will have a single queen. One queen is not enough to form a triple of three queens, so we continue to the next row. With the second row now in our “window,” we still don’t have enough queens to form a triple. Adding the third row to our window increases our total queens to three, giving us our first triple. We’ll number our queens using their zero-based row indices:

queens = [2,1,0]

and formulate our selection of triples as combinations: we have three queens and we want to choose three of them in all possible ways, which yields only one way:

${[2,1,0] \choose 3} = [(2, 1, 0)]$

For n = 4, we’d have:

queens = [3,2,1,0]

with four possible ways to choose three queens among the four total:

${[3,2,1,0] \choose 3} = [(3,2,1), (3,2,0), (3,1,0), (2,1,0)]$

For n = 5, we’d have ten triples, and so on. It should be clear that, in general, ${n \choose 3}$ tells us how many queen triples we’ll need to check on our board: if any of these triples contains three queens that all lie on the same line, the configuration is not a valid solution.

Running the solver now to solve the vanilla version of the problem for n = 5, and with pretty printing of each solution turned on, we see the following ten solutions:

x0 = 0 x1 = 2 x2 = 4 x3 = 1 x4 = 3 
Q _ _ _ _ 
_ _ Q _ _ 
_ _ _ _ Q 
_ Q _ _ _ 
_ _ _ Q _ 

x0 = 0 x1 = 3 x2 = 1 x3 = 4 x4 = 2 
Q _ _ _ _ 
_ _ _ Q _ 
_ Q _ _ _ 
_ _ _ _ Q 
_ _ Q _ _ 

x0 = 1 x1 = 4 x2 = 2 x3 = 0 x4 = 3 
_ Q _ _ _ 
_ _ _ _ Q 
_ _ Q _ _ 
Q _ _ _ _ 
_ _ _ Q _ 

x0 = 2 x1 = 4 x2 = 1 x3 = 3 x4 = 0 
_ _ Q _ _ 
_ _ _ _ Q 
_ Q _ _ _ 
_ _ _ Q _ 
Q _ _ _ _ 

x0 = 2 x1 = 0 x2 = 3 x3 = 1 x4 = 4 
_ _ Q _ _ 
Q _ _ _ _ 
_ _ _ Q _ 
_ Q _ _ _ 
_ _ _ _ Q 

x0 = 3 x1 = 0 x2 = 2 x3 = 4 x4 = 1 
_ _ _ Q _ 
Q _ _ _ _ 
_ _ Q _ _ 
_ _ _ _ Q 
_ Q _ _ _ 

x0 = 3 x1 = 1 x2 = 4 x3 = 2 x4 = 0 
_ _ _ Q _ 
_ Q _ _ _ 
_ _ _ _ Q 
_ _ Q _ _ 
Q _ _ _ _ 

x0 = 4 x1 = 1 x2 = 3 x3 = 0 x4 = 2 
_ _ _ _ Q 
_ Q _ _ _ 
_ _ _ Q _ 
Q _ _ _ _ 
_ _ Q _ _ 

x0 = 4 x1 = 2 x2 = 0 x3 = 3 x4 = 1 
_ _ _ _ Q 
_ _ Q _ _ 
Q _ _ _ _ 
_ _ _ Q _ 
_ Q _ _ _ 

x0 = 1 x1 = 3 x2 = 0 x3 = 2 x4 = 4 
_ Q _ _ _ 
_ _ _ Q _ 
Q _ _ _ _ 
_ _ Q _ _ 
_ _ _ _ Q 


Solutions found : 10

Looking at each of these solutions, you’ll see that none of them are valid solutions to our modified problem: they each have a triple of queens that forms a line from one side of the board to the other. Each of these triples is described by one of the combination triples detailed above. Now we can start to see our constraint taking shape: for each queen triple (m, n, o), the slope of the line segment between queens m and n must not equal the slope of the line segment connecting queen n to o. More formally, and destructuring each queen into its row and column coordinates:

\( m \to (u, v) ; n \to (w, x) ; o \to (y, z) \)

\( \frac{u - w}{v - x} \ne \frac{w - y}{x - z} \)

More concretely, each queen is stored in an array indexed by its row and containing its column:

\( m \to (m, queens[m]) ; n \to (n, queens[n]) ; o \to (o, queens[o]) \)

\( \frac{m - n}{queens[m] - queens[n]} \ne \frac{n - o}{queens[n] - queens[o]} \)

Ideally we would just enter this verbatim as a new solver constraint and move on were it not for the fact that the solver only operates over integers. The divisions here are forbidden as they result in floating point numbers. Thankfully we can cross-multiply the fractions and eliminate the division:

\( (m - n) \bullet (queens[n] - queens[o]) \ne (n - o) \bullet (queens[m] - queens[n]) \)

This is our final constraint. Putting it all together, we add this Python code immediately after the for loop that adds the diagonal constraints to the solver:

from itertools import combinations
for queentrio in (list(combinations(range(board_size-1,-1,-1), 3))):
    m,n,o = queentrio
    model.Add((m-n)*(queens[n]-queens[o]) != (n-o)*(queens[m]-queens[n]))

Now when we re-run the solver for n = 5, we get no solutions as expected:

Solutions found : 0

It isn’t until n = 8 that we get a non-empty solution set:

x0 = 3 x1 = 1 x2 = 7 x3 = 4 x4 = 6 x5 = 0 x6 = 2 x7 = 5 
_ _ _ Q _ _ _ _ 
_ Q _ _ _ _ _ _ 
_ _ _ _ _ _ _ Q 
_ _ _ _ Q _ _ _ 
_ _ _ _ _ _ Q _ 
Q _ _ _ _ _ _ _ 
_ _ Q _ _ _ _ _ 
_ _ _ _ _ Q _ _ 

x0 = 5 x1 = 1 x2 = 6 x3 = 0 x4 = 3 x5 = 7 x6 = 4 x7 = 2 
_ _ _ _ _ Q _ _ 
_ Q _ _ _ _ _ _ 
_ _ _ _ _ _ Q _ 
Q _ _ _ _ _ _ _ 
_ _ _ Q _ _ _ _ 
_ _ _ _ _ _ _ Q 
_ _ _ _ Q _ _ _ 
_ _ Q _ _ _ _ _ 

x0 = 2 x1 = 5 x2 = 7 x3 = 1 x4 = 3 x5 = 0 x6 = 6 x7 = 4 
_ _ Q _ _ _ _ _ 
_ _ _ _ _ Q _ _ 
_ _ _ _ _ _ _ Q 
_ Q _ _ _ _ _ _ 
_ _ _ Q _ _ _ _ 
Q _ _ _ _ _ _ _ 
_ _ _ _ _ _ Q _ 
_ _ _ _ Q _ _ _ 

x0 = 2 x1 = 4 x2 = 7 x3 = 3 x4 = 0 x5 = 6 x6 = 1 x7 = 5 
_ _ Q _ _ _ _ _ 
_ _ _ _ Q _ _ _ 
_ _ _ _ _ _ _ Q 
_ _ _ Q _ _ _ _ 
Q _ _ _ _ _ _ _ 
_ _ _ _ _ _ Q _ 
_ Q _ _ _ _ _ _ 
_ _ _ _ _ Q _ _ 

x0 = 2 x1 = 6 x2 = 1 x3 = 7 x4 = 4 x5 = 0 x6 = 3 x7 = 5 
_ _ Q _ _ _ _ _ 
_ _ _ _ _ _ Q _ 
_ Q _ _ _ _ _ _ 
_ _ _ _ _ _ _ Q 
_ _ _ _ Q _ _ _ 
Q _ _ _ _ _ _ _ 
_ _ _ Q _ _ _ _ 
_ _ _ _ _ Q _ _ 

x0 = 5 x1 = 3 x2 = 0 x3 = 4 x4 = 7 x5 = 1 x6 = 6 x7 = 2 
_ _ _ _ _ Q _ _ 
_ _ _ Q _ _ _ _ 
Q _ _ _ _ _ _ _ 
_ _ _ _ Q _ _ _ 
_ _ _ _ _ _ _ Q 
_ Q _ _ _ _ _ _ 
_ _ _ _ _ _ Q _ 
_ _ Q _ _ _ _ _ 

x0 = 5 x1 = 2 x2 = 0 x3 = 6 x4 = 4 x5 = 7 x6 = 1 x7 = 3 
_ _ _ _ _ Q _ _ 
_ _ Q _ _ _ _ _ 
Q _ _ _ _ _ _ _ 
_ _ _ _ _ _ Q _ 
_ _ _ _ Q _ _ _ 
_ _ _ _ _ _ _ Q 
_ Q _ _ _ _ _ _ 
_ _ _ Q _ _ _ _ 

x0 = 4 x1 = 6 x2 = 0 x3 = 3 x4 = 1 x5 = 7 x6 = 5 x7 = 2 
_ _ _ _ Q _ _ _ 
_ _ _ _ _ _ Q _ 
Q _ _ _ _ _ _ _ 
_ _ _ Q _ _ _ _ 
_ Q _ _ _ _ _ _ 
_ _ _ _ _ _ _ Q 
_ _ _ _ _ Q _ _ 
_ _ Q _ _ _ _ _ 


Solutions found : 8

Going through each board configuration in the solution set above, we can see that no three queens form a straight line. So far so good.

Rolling Some Code

Of course, a constraint solver isn’t necessary to solve the n queens problem, even with the extra twist enforcing noncollinearity. It does, however, give you some reassurance that your solution is correct. Here I present one such solution, and to keep this as concise as possible, I’m omitting the code that drives the backtracking; the Internet is already filled with various incarnations of that piece, so I’m just going to focus on writing the function that checks whether each placement of a queen by the backtracking algorithm is valid:

private static boolean isValidMove(int n, int row, int col, int[] positions) {

  // ... column and diagonal checks ommitted for brevity ...

  // Check collinearity: pair this queen with each preceding queen; no need to
  // pair with first row because no points before it can be extrapolated.
  for (int r = row - 1; r > 0; r--) {
    int thisqueen_r = row, thisqueen_c = col;
    int prevqueen_r = r, prevqueen_c = positions[r];
    int rise = thisqueen_r - prevqueen_r;
    int run = thisqueen_c - prevqueen_c;
    // Extrapolate to points in rows above prevqueen until we run off the board;
    // if any of those points are occupied by a queen, we have three collinear.
    for (int multiple = 1; prevqueen_r - multiple*rise >= 0; multiple++) {
      int extrap_r = prevqueen_r - multiple*rise;
      int extrap_c = prevqueen_c - multiple*run;
      if (extrap_r >= 0 && extrap_r < n && extrap_c >= 0 && extrap_c < n
          && positions[extrap_r] == extrap_c) {
        return false;
      }
    }
  }

  return true;
}

The code enforcing the classical requirements of this problem is simple and has been omitted for brevity. Following it, we have a for loop that enforces noncollinearity by pairing the newly placed queen with each queen in the rows preceding it. It then calculates the slope between the two queens and extrapolates the line out across the preceding rows until it runs off the board; notice that we don’t have to extrapolate across succeeding rows because the backtracking algorithm (at least as was implemented with this code) only places queens in order from the lowest to the highest row. If at any point the extrapolated line crosses a space occupied by a third queen, a collinear triple of queens has been found and the move is rendered invalid.

Can you spot the subtle mistake? If not, we’ll use the constraint solver to do it for us. First we translate the constraint we defined above from Python into Java, which becomes somewhat verbose due to Java’s static typing (note that Combinations here is provided by the Apache Commons Math library):

// No three queens should be collinear.
if (dimension >= 3) {
  Combinations queentrios = new Combinations(dimension, 3);
  for (int[] queentrio : queentrios) {
    int m = queentrio[2];
    int n = queentrio[1];
    int o = queentrio[0];
    IntVar m_sub_n = solver.makeIntVar(m - n, m - n, "m"+m+"_sub_n"+n);
    IntVar n_sub_o = solver.makeIntVar(n - o, n - o, "n"+n+"_sub_o"+o);
    solver.addConstraint(solver.makeNonEquality(
          solver.makeProd(m_sub_n, solver.makeDifference(q[n], q[o])),
          solver.makeProd(n_sub_o, solver.makeDifference(q[m], q[n]))));
  }
}

Then integrate this into the Java version of the solver, which is available as NQueens2.java in the source tarball of Google OR Tools at their downloads page). Writing a simple JUnit test that calls our own code alongside the constraint solver and asserts equality between the solution sets returned by both, we get:


> Task :test FAILED

nqueenswithatwist.AppTest > testDimensions STANDARD_OUT
    Testing dimension=1...
    Solving with our code...
    Our code found 1 solutions.
    Solving with constraint solver...
    Constraint solver found 1 solutions.
    Comparing solution sets...
    Solution sets are identical.
    Done testing dimension=1.

    Testing dimension=2...
    Solving with our code...
    Our code found 0 solutions.
    Solving with constraint solver...
    Constraint solver found 0 solutions.
    Comparing solution sets...
    Solution sets are identical.
    Done testing dimension=2.

    Testing dimension=3...
    Solving with our code...
    Our code found 0 solutions.
    Solving with constraint solver...
    Constraint solver found 0 solutions.
    Comparing solution sets...
    Solution sets are identical.
    Done testing dimension=3.

    Testing dimension=4...
    Solving with our code...
    Our code found 2 solutions.
    Solving with constraint solver...
    Constraint solver found 2 solutions.
    Comparing solution sets...
    Solution sets are identical.
    Done testing dimension=4.

    Testing dimension=5...
    Solving with our code...
    Our code found 0 solutions.
    Solving with constraint solver...
    Constraint solver found 0 solutions.
    Comparing solution sets...
    Solution sets are identical.
    Done testing dimension=5.

    Testing dimension=6...
    Solving with our code...
    Our code found 0 solutions.
    Solving with constraint solver...
    Constraint solver found 0 solutions.
    Comparing solution sets...
    Solution sets are identical.
    Done testing dimension=6.

    Testing dimension=7...
    Solving with our code...
    Our code found 0 solutions.
    Solving with constraint solver...
    Constraint solver found 0 solutions.
    Comparing solution sets...
    Solution sets are identical.
    Done testing dimension=7.

    Testing dimension=8...
    Solving with our code...
    Our code found 12 solutions.
    Solving with constraint solver...
    Constraint solver found 8 solutions.
    Comparing solution sets...
     ------------------------
    | *  Q  *  *  *  *  *  * |
    | *  *  *  *  *  *  !  * |
    | *  *  *  *  !  *  *  * |
    | *  *  *  *  *  *  *  Q |
    | !  *  *  *  *  *  *  * |
    | *  *  *  Q  *  *  *  * |
    | *  *  *  *  *  Q  *  * |
    | *  *  Q  *  *  *  *  * |
     ------------------------
     ------------------------
    | *  *  *  Q  *  *  *  * |
    | *  !  *  *  *  *  *  * |
    | *  *  *  *  *  *  Q  * |
    | *  *  !  *  *  *  *  * |
    | *  *  *  *  *  Q  *  * |
    | *  *  *  *  *  *  *  Q |
    | Q  *  *  *  *  *  *  * |
    | *  *  *  *  !  *  *  * |
     ------------------------
     ------------------------
    | *  *  *  *  Q  *  *  * |
    | *  *  *  *  *  *  !  * |
    | *  Q  *  *  *  *  *  * |
    | *  *  *  *  *  !  *  * |
    | *  *  Q  *  *  *  *  * |
    | Q  *  *  *  *  *  *  * |
    | *  *  *  *  *  *  *  Q |
    | *  *  *  !  *  *  *  * |
     ------------------------
     ------------------------
    | *  *  *  *  *  *  Q  * |
    | *  !  *  *  *  *  *  * |
    | *  *  *  !  *  *  *  * |
    | Q  *  *  *  *  *  *  * |
    | *  *  *  *  *  *  *  ! |
    | *  *  *  *  Q  *  *  * |
    | *  *  Q  *  *  *  *  * |
    | *  *  *  *  *  Q  *  * |
     ------------------------

nqueenswithatwist.AppTest > testDimensions FAILED
    java.lang.AssertionError at AppTest.java:52
3 actionable tasks: 1 executed, 2 up-to-date

Everything matches up until n = 8, at which point the hand-rolled code returns 12 solutions while the constraint solver returns 8. The four extra boards found by the hand-rolled code are pretty-printed above. What’s the problem with these? Upon close inspection, it turns out that each has a collinear trio of queens, with one pair separated by (1, 2) units of distance and the other by (2, 4) units of distance. (To help make this clear, I’ve replaced the “Q” of each such trio of queens with the symbol “!” above). Despite these pairs having the same slope, the hand-rolled code doesn’t mark these boards as invalid.

(Notice that these four boards are symmetrical; they are actually a single board configuration accompanied by its three rotations. It’s possible to solve the n queens problem with the added constraint that solutions are not symmetrical, but that’s not in play here.)

The reason for the discrepancy lies in the code that calculates the slope components:

int rise = thisqueen_r - prevqueen_r;
int run = thisqueen_c - prevqueen_c;
for (int multiple = 1; prevqueen_r - multiple*rise >= 0; multiple++) {
      int extrap_r = prevqueen_r - multiple*rise;
      int extrap_c = prevqueen_c - multiple*run;
...

The variables rise and run form an implicit ratio that is not reduced here. If we calculate a slope of 2/4 and start with a multiple of 1, the next point we’ll extrapolate to will be (2, 4) units of distance away. Really we should start at the point (1, 2) units of distance away, then visit the point (2, 4) units away, etc. The solution of course is to take the greatest common factor of the numerator and denominator to reduce the slope first before extrapolating:

...
int gcf = Math.abs(GCF(rise, run));
rise /= gcf;
run /= gcf;
for (int multiple = 1; ...) {

That fix will bring the code into agreement with the constraint solver; testing for values of n up to 15, the code and solver produce identical solution sets:

Board Dimension          Solutions
1 1
2 0
3 0
4 2
5 0
6 0
7 0
8 8
9 32
10 40
11 96
12 410
13 1392
14 4416
15 18752

This particular situation interested me because a constraint solver afforded something that individual handwritten tests would not have otherwise: a comprehensive assurance that both the code and the solver are performing as desired in a way that scales up to any value of n, without relying upon just a few cases of n. And as with the analysis of the four invalid boards above for n = 8, running the code side-by-side with the solver provides a way to diff the results to quickly determine where the problem is. Were this part of a system developed over the long-term, the halves would reinforce each other; a regression error in either the code or in the solver’s constraint definitions would trigger test failures with specific differentiating information hopefully pointing the way back to the change at fault.