Solver basics

In the previous post I’ve given a quick overview of what the solver is about, and in this post I’ll dive a little bit deeper into the subject, using N-queens with just 4 queens as an example problem. More specifically, I’ll fully specify the problem by defining the variables and constraints, and then walk through what a simple search would do, ultimately finding a solution.

Closer look at N-queens problem

To recap the previous post, the goal of solving the N-queens problem is to find a way to place N queens on an NxN chessboard in a way that the queens are not attacking each other. I also mentioned that a common way of modeling this problem is by having over variable per queen, where variable M represents the queen in column M, and this model choice effectively ensures that no pair of queens share the same column. One thing I omitted earlier is that each variable is also associated with its domain, which is basically the set of values that could be assigned to the variable. For N-queens the domain of all variables is {1, …, N}. A value from this domain simply represents the row, from 1 to N, that a particular queen is assigned to.

Constraints for N-queens get a little bit more interesting: by the definition of variables we know that no pair of queens will attack each other vertically, since they cannot share the same column, but we still need to make sure they will not attack each other horizontally and diagonally.

• Preventing horizontal attacks is the same thing as making sure that each queen is assigned to a different row, and this is a perfect example of applying the all-different constraint. There are different ways of implementing such a constraint, but the net outcome is the same - all variables that are part of such a constraint must be assigned to different values. So we’ll define one all-different constraint and apply it to all of the 4 queens, as this prevents them from horizontally attacking each other.
• Preventing diagonal attacks will require doing a bit of math to define the constraint: we know that a pair of queens share a diagonal if we can draw a line between them with a slope of 1 or -1, and we want to prevent that. Using the “rise over run” formula we can express that as $$abs((y_2-y_1) / (x_2 - x_1)) \ne 1$$ Let’s get rid of division, because dealing with floats is not fun: $$abs(y_2 - y_1) \ne abs(x_2-x_1)$$ With that, we just need to add constraints for each pair of queens, so that gives us $${n \choose 2} = n(n-1)/2$$ binary constraints.

This completes the definition of an N-queens problem.

Search and N-queens

Now that we’ve defined the N-queens problem, let’s see what searching for a solution looks like. We’ll look at the smallest non-trivial N-queens problem with a solution, which happens to be with 4 queens.

There are a couple more things to mention about search:

• Making the right decisions during search is critical. For this, typically two types of heuristics are used: variable ordering heuristics, which I mentioned in the previous post, and value ordering heuristics. They tell search which variable to assign next, and to what value. Here we’ll assume that both are using lexicographic ordering, meaning we’ll assign queen in column 1 first (call it Q1), then in columns 2, 3 and finally 4. We’ll do the same for values; i.e., rows that we assign the queens to.
• The other thing done during search is called constraint propagation, which basically says “after search assigns a value, it will proactively adjust other unassigned variables by removing values that would break a constraint”. That might sound a bit complicated, so for now, we’ll assume that we don’t do this, and only evaluate constraints when picking the next value.

We can now look at the example search for the 4-queens problem:

In the diagram above, labels next to nodes represent the decision made to reach the node (aside from root node); e.g.; “Q2:3” means “assign queen in column #2 to row 3”. Because we are using lexicographic variable ordering you’ll also note that each level in the tree corresponds to assigning the next queen. In cases where we find it impossible to assign a value to the next queen without violating a constraint, we’ll label those with “X”; e.g., “Q4:X” means “we couldn’t place queen in column 4 as every possible spot is already under attack”. Those are always followed by a backtrack.

Explaining search steps

• Start with no decisions made at the root of the search tree.
• Assign Q1 to 1; i.e., to place queen in column #1 on row #1. Then create a new child node and step into it.
• Now we’ll assign Q2. Placement of Q1 means that Q2 cannot be on row #1 (horizontal constraint, aka all different constraint, is violated) or on row #2 (diagonal constraint is violated). So we’ll place it on row #3, create another child node, and step into it.
• Now we’re attempting to assign Q3. This is where things get more interesting: row #1 is under attack by Q1, and rows #2 through #4 are under attack by Q2. No decision can be made and we’ve hit a dead end. This is where backtracking must take place, which basically means going back to the parent of the current node and stating that the decision it made earlier leads to no solutions. This is the leftmost leaf node with an X on it in the diagram.
• We’re now back to finding a new value for Q2, as assigning it to row #3 didn’t work. Search will try row #4, and, as usual, create a child node for that and step into it.
• We’re trying to assign Q3 again. Row #1 is still under attack by Q1, however, now that we’ve moved Q2 to row #4, Q3 can go on row #2. We’ll make this decision, create a new child node, and step into that.
• We’re now down to our last queen - Q4! Alas, looking for a viable place to put it we’ll see that row #1 is taken by Q1, row #2 by Q3, row #3 is under attack diagonally by Q3, and row #4 is already taken by Q2. We cannot place Q4 without attacking one of the other queens, and we must backtrack.
• Q3 must be moved from row #2, but it has nowhere else to go - we can’t place it on row #3 because Q1 attacks that diagonally, and #4 is already under attack by Q2. We must backtrack again.
• Q2 must now be moved from row #4, but Q2 has exhausted possible places it could be placed, so we backtrack once again, and end up at the root node.
• After all that work we learned that Q1 cannot be on row #1 and we’re back at the root node. We must try the next value, row #2, create a new child and step into it. Thankfully, the rest of the search is backtrack-free.
• Q2 can only be on row #4 because Q1 attacks all others. So we place it, create a new child and step into that.
• Q3 can only be on row #1 now. We do that, and create a new child + step into that again.
• Q4 is last, and luckily it can be placed on row #3. All the variables are now assigned and none of the constraints are violated, and thus we have a solution!

Side-note: my solver always makes binary decisions, so the logic would have been more like “try X, and if that fails, try not X”. The net result would still be the same, but we would have a few more nodes in the search tree. I’ll cover the more exact mechanics of my solver separately.

Summary

We’ve looked at how N-queens problem can be modeled as a constraint satisfaction problem, and how search traverses the search space by incrementally building up a search tree. We saw how the constraints prevent us from visiting parts of the tree that have no solutions, and how we recover from failure to find a solution in subtrees.