The N-Queens Puzzle and Recursion

One of the cooler exercises from the Structure and Interpretation of Computer Programs is Exercise 2.42: finding solutions to the N-Queens Puzzle.

The N-Queens Puzzle is a sort of chess puzzle. Suppose we have an NxN chessboard, and N queen pieces. We want to find a way to position the pieces so that none of the queens can capture each other. In fact, we want to find all possible ways to do this.

Over the next couple of blog posts, we'll consider two techniques for getting a grasp on this puzzle:

• Today, we'll look at a recursive method that constructs the set of all feasible solutions by building them up a column at a time, which we'll implement using Clojure.
• In the next post, we'll see how we can formulate the N-Queens puzzle as a 0-1 Integer Linear Program (ILP), which we can solve using Java in conjunction with some open source operations research tools; namely the SCPSolver with the GNU Linear Programming Kit (GLPK).

A Brief Chess Refresher

Before all that though, let's make sure that we fully understand the problem first!

What makes the puzzle difficult is that in chess, the queen piece is the one with the most directions of attack. From its square, it can capture pieces by moving along the same row (left/right), by moving along the same column (up/down), and also by moving along any diagonal.

In essence, the queen can move in any compass direction on the chessboard.

Our goal is to position the queens on the chessboard in such a way that they can't capture each other (where we say that one queen can "capture" another if it can move to the other queen's square along any of its movement directions). So computationally, a solution to the N-Queens puzzle is a configuration of the chessboard, where:

• We have exactly N queens positioned on the board.
• There is exactly one queen in every row,
• There is exactly one queen in every column,
• Given a queen, we should not be able to capture another queen by moving diagonally in any direction.
  (An equivalent rule which will be useful for our ILP formulation in the next post:
     Any diagonal we could draw over the board should hit at most one queen.)

Now depending on what N is, there may be many different solutions, or even none at all!

Constructing the Solutions Recursively

We can actually generate the set of all solutions to the N-Queens Puzzle by considering a column of the chessboard at a time. We'll work our way across the board from left to right, collecting the valid partial solutions as we go.

And we can do this with a recursive algorithm!

Suppose for a second that we're just about done – we've only got the right-most column to go. That is, suppose we've checked N-1 columns and built up the list of all partial solutions: where N-1 queens are positioned in those N-1 columns so that none of them can capture each other.

Then we can get the complete solutions by basically copying the list of solutions N times, and in each instance, adding the new queen for the Nth column into a different row for those solutions. So in our first copy of the list we add the new queen to the 1st row for each solution, in the second copy we add the queen to the 2nd row, and so on.

So in effect, we will have taken each of the partial solutions and duplicated them N times, with the new queen placed into a different row for each copy.

Finally, for each solution in each list, we need to check that the added queen isn't in check with any of the existing queens. But if all is well, then we've found all of the possible solutions for the puzzle!

So that's our process for adding on the Nth column. But what about the second-to-last step?

Let's again assume that we've got the list of all partial solutions for N-2 queens positioned on the first N-2 columns at this point. To get to the partial solutions for N-1 columns, we simply employ that exact same process that we described above! That is, we copy all of the partial solutions we have N times, add a new queen to each of the different rows in the (N-1)th column, and filter for the new feasible solutions.

Now we apply this same logic over and over again recursively:

• We use this process to generate the N-2 column partial solutions given the N-3 column partial solutions,
• We can find the N-3 column partial solutions using this process if we have the N-4 ones,
• ... and so on.

Eventually we reach the base case for the N-N column partial solutions, where we want to position 0 queens in 0 columns. This case has a trivial solution – the empty list.

And this fully describes our algorithm. Given a non-negative integer N, we do the following:

1. If N=0, we return our base case, the empty list.
2. Otherwise:
1. We fire off a recursive call to get the list of partial solutions for the first N-1 columns. 
2. We duplicate each partial solution N times, each time adjoining the Nth column with the new queen in a different row.
3. We then check each solution to make sure that the newest queen is "safe". These will be the feasible (partial) solutions, which are returned by this call.

So that's the top level. There are still a few details to work out obviously, but they'll be more specific to our actual Clojure code implementation.

The Details (in Clojure)

So first off, we should decide what data representation we want to use for a solution. Since we're really only concerned with the row and column position for each of the queens, we can simply represent a solution as a list of (row, column) pairs.

So in terms of our Clojure code, when we want to adjoin the new queen's (row, column) position to the existing partial solution, we can simply cons on a new list containing the row and column. Then the adjoin-position function looks like the following:

     (defn adjoin-position [row column positions]
       (cons (list row column) positions))

With that decided, we pretty much know how our solution data is going to look at every step of the program, so we can actually write up our main recursive method. As per the one given in the SICP book, our procedure looks like this:

     (defn queens [n]
       (defn queen-cols [k]
         (if (zero? k)
           (list nil)
           (filter
            (fn [positions] (safe? k positions))
            (mapcat 
             (fn [rest-of-queens]
               (map (fn [new-row]
                      (adjoin-position new-row k rest-of-queens))
                    (range 1 (inc n))))
             (queen-cols (dec k))))))
       (queen-cols n))

Looks a bit cryptic, but here we actually have a direct implementation of our top-level algorithm. We start off the stack of recursive calls by calling the interior function queen-cols with our value of n. The queen-cols procedure checks its argument k and returns the empty solution list if k is 0.

If k is not 0, then we recursively call queen-cols with the argument k-1 to solve for the columns on the left. Assuming that our recursive procedure works, this call will then return us the list of partial solutions for the first k-1 columns.

Given this list of partial solutions, we then execute the following slightly tricky sequence of steps:

• Assume for a moment that we have a placeholder variable rest-of-queens that points to our partial solution of interest. We define a closure that takes in a row number, new-row, and adjoins the new queen position (new-row, k) to the rest-of-queens solution.
• We then map that closure over the list of all possible row numbers 1, 2, 3, ..., n. This effectively duplicates our solution n times, where each copy of the solution has the new queen in a different row.
• In fact, we isolate this mapping process: we define another closure function that takes in a partial solution, rest-of-queens, and applies this mapping.
• Then we want to map this closure across the list of partial solutions. The closure takes in each partial solution and returns lists of augmented partial solutions, which we want to accumulate into a new solution list. We can do this in Clojure using the mapcat function.
• The result of this slightly convoluted process is that we end up with a new list of potential solutions, duplicated for each possible position for the new queen.

With that done, the last thing to do is filter our solution list to make sure that the new queen isn't in check with any of the others, which we can handle with a call to the yet-to-be-defined safe? function.

So the last detail we need to work out is our concept of when a new queen is "safe" with respect to the existing queens in a given (partial) solution. And in fact, we only ever have to check for the safety of the newest queen – the fact that we've built our solution up recursively means that all of the prior queens will already be safe.

As you can see from the way we defined it in the main procedure, our safe? function will take the column number and the new potential solution, and should return true if the newest queen is in check with any of the others.

So to do this, we first need to isolate the newest queen from the existing queens (this is pretty straight-forward: our newest queen will be the one in the given column), and then test for whether the newest queen is in check. If we have an ancillary function queens-in-check? that takes two queens and determines this for us, then we can use this function to filter the list of other queens, leaving behind only those that are in check with the newest queen. Then we simply return true (ie. "safe") if that list is empty. 

     (defn safe? [column positions]
       (let [newest-queen
             (first (filter 
                     (fn [position] (= (second position) column))
                     positions))
             other-queens
             (remove (fn [position] (= newest-queen position))
                     positions)]
         (empty? (filter 
                  (fn [queen] (queens-in-check? newest-queen queen))
                  other-queens))))

Perfect! Now all we need is an implementation for the queens-in-check? function. As per the rules of chess that we briefly mentioned above, two queens are in check if they are in the same row, in the same column, or on the same diagonal.

Now we don't have to check the column case at all, since we're only ever adding a single queen to each column as we work across. So our queens-in-check? function simply returns true if either the queens are in the same row, or if they are on the same diagonal:

     (defn queens-in-check? [q1 q2]
       (or (same-row? q1 q2)
           (same-diagonal? q1 q2)))

So we implement these last two functions same-row? and same-diagonal?, and we're done!

The row case is simple enough. Since we represent a queen position as (row, column), we simply test for whether the first number in the pair (ie. the row) is the same between the two queens: 

     (defn same-row? [q1 q2]
       (= (first q1) (first q2)))

Now for the same diagonal case, we can observe the following.

Suppose we have a queen at position (i,j). Then:

• A queen that is on the diagonal to the right and down from this queen is at position (i+x,j+x) for some number x.
• A queen to the right and up diagonally is at position (i-x,j+x),
• A queen to the left and up diagonally is at position (i-x,j-x),
• A queen to the left and down diagonally is at position (i+x,j-x).

In all of these cases, subtracting the queen's position from any of the others leaves us with
(±x,±x) as a result! That is, the first and second numbers of this pair have the same magnitude (we disregard the sign.)

So we can write up our last function same-diagonal? to do this calculation (we also define an abs absolute value procedure here to help us.)

     (defn same-diagonal? [q1 q2]
       (defn abs [x]
         (if (neg? x)
           (- x)
           x))
       (= (abs (- (first q1) (first q2)))
          (abs (- (second q1) (second q2)))))

And with that, we're done!

Solving the N-Queens Puzzle

So when we put everything together (and make it look pretty with documentation and some tidying up), we get the following:


Alright! Let's see how it handles the N=4 (ie. 4x4 chessboard) case:

     (queens 4)
     ;> (((3 4) (1 3) (4 2) (2 1)) ((2 4) (4 3) (1 2) (3 1)))

Nice! We can see the two solutions right there. They correspond to the following board configurations (the black X's are queens, the O's are unoccupied squares):

     O O X O     O X O O
     X O O O     O O O X
     O O O X     X O O O
     O X O O     O O X O

How about for a regular 8x8 chessboard?

     (queens 8)
     ;> (((4 8) (2 7) (7 6) (3 5) (6 4) (8 3) (5 2) (1 1)) ((5 8)
     ;>  (2 7) (4 6) (7 5) (3 4) (8 3) (6 2) (1 1)) ((3 8) (5 7)
     ;>  (2 6) (8 5) (6 4) (4 3) (7 2) (1 1)) ((3 8) (6 7) (4 6)
     ;>  (2 5) (8 4) (5 3) (7 2) (1 1)) ((5 8) (7 7) (1 6) (3 5) 
     ;>  (8 4) (6 3) (4 2) (2 1)) ((4 8) (6 7) (8 6) (3 5) (1 4)
     ;>  ...
     ;>  ...

We get a whole lot of solutions! If we look at just the first two, we have the following chessboard configurations...

     X O O O O O O O       X O O O O O O O
     O O O O O O X O       O O O O O O X O
     O O O O X O O O       O O O X O O O O
     O O O O O O O X       O O O O O X O O
     O X O O O O O O       O O O O O O O X
     O O O X O O O O       O X O O O O O O
     O O O O O X O O       O O O O X O O O
     O O X O O O O O       O O X O O O O O

And finally, we can use our functions to verify that the N=2 and N=3 cases have no solutions at all.

     (queens 2)
     ;> ()
 
     (queens 3)
     ;> ()


So we've seen how we can use recursion to obtain all of the solutions to the N-queens puzzle. Of course, you can imagine that this gets computationally expensive as the size of our chessboards gets larger! 

Next time we'll see how we can instead formulate the N-Queens Puzzle as an integer linear programming problem, which will allow us to use the tools of operations research to arrive at a single solution instead.