Eight Queens

The Eight Queens puzzle is a classic problem for computer programmers. The goal is to find all the ways to place eight queens on an 8-by-8 chess board such that no two queens threaten each other. The problem can be generalized to N-Queens on an N-by-N board. The Wikipedia article has a good discussion and lots of interesting links. If you’re working on a homework assignment, you should start there before you borrow my code.

I’m a Clojure programmer so this article is going to explore some Clojure solutions. You can find examples in many languages at the Rosetta Code website, including a simple one written in Clojure. Here’s a slightly modified version:

(require '[clojure.math.combinatorics :as c])

(defn rosetta-queens [n]
  (filter (fn [x] (every? #(apply distinct? (map-indexed % x)) [+ -]))
          (c/permutations (range n))))

Typically, the chess board is represented as a two-dimensional array of positions in rows and columns. A brute force seach of every possible arrangement of 8 queens on 64 possible positions is intractable. The search space can be constrained by restricting the possible arrangements such that no two queens can occupy the same row. That reduces the problem to finding a column for each queen, with the intuitive understanding that there will be one queen per row. Instead of explicitly listing the two-dimensional coordinates, we can specify a vector of column numbers, with the index of each element implying the row number. For example, a 4-queens solution might be ([0 1] [1 3] [2 0] [3 2]) in two-dimensional notation. The equivalent state is represented in one dimension as [1 3 0 2]. The rosetta-queens and most other solutions return the single vector result, and we will follow that convention.

Let’s take a minute to review the rosetta-queens function. We want to arrange the queens so that no two share the same row, column or either of the diagonals. In other words, a solution will have distinct assignments for each of those aspects. The rows are naturally distinct because they are simply the indices of the vector. The columns are obviously distinct as they are generated from permutations of the range expression. Thus, rosetta-queens generates candidates that are safe in terms of rows and columns, but it still has to check if the diagonals cause conflicts.

It turns out that the sums and differences of the two-dimensional coordinates correspond to the two diagonals. Notice that two-dimensonal coordinates [1, 2] and [4, 5] are on the same diagonal – their differences are equal. Similarly, [0, 4] and [2, 2] threaten each other and their sums are the same. Another way of thinking about diagonals is to say that the slope between the positions must have an absolute value of 1. Points [a, b] and [c, d] threaten each other if (= (Math/abs (- a c)) (Math/abs (- b d))).

The rosetta-queens solutions uses the map-indexed expression to get the row (as the index) and the column from the candidate vector. The every? expression checks both + and - of those coordinates to check the two possible diagonals. If all the diagonal calculations are distinct for the queens, then we have a solution.

The rosetta-queens function is nice and short. It uses built-in Clojure functions, plus just one imported function permutations from the standard contribution library. I think this is a pretty good solution. Its performance is acceptable and it’s not too hard to comprehend what it’s doing once you see how the math works.

Naturally, there are a number of more efficient approaches. The first possible improvement that comes to mind is to try for a more incremental generation of positions. After you place a queen in one row, many positions in other rows can be ruled out. If you add queens sequentially to partial solutions, you can generate a set of solutions more efficiently than evaluating all the permuations.

After doing some experiments, I came up with my own solution in Clojure. I doubt there’s really anything new here as people have been working on the Eight Queens puzzle for over a century. In any case, I had fun trying out a few ideas and I thought I might share my results here.

As we build up the solution by making assignments in row order, we need to evaluate the possible positions in the next row. For each position of row and column, we want a fast way to check for conflicts with previously assigned queens. The basic idea is to encode the column and diagonal markers for each position using bits in a long. The current state of the board is just the bit-or of the previous state with the new queen’s position suitably encoded. Conflicts can be found with a bitwise check. Clojure is not known as a bit-twiddling language, but all the bit functions you need are available.

Of course, we need to have non-overlapping codes for the diagonals and columns so we can set the bits independently. My little trick is to do the sums and differences with an extra argument of the dimension. An N-dimensional board has 2N - 1 diagonals in each direction. With a 64-bit long, there are enough bits to hold the state of a 13 x 13 board – that’s 13 column bits + 25 bits for one diagonal + 25 bits for the other. By the way, the bit-set with a negative index works the way you would want it to – #(mod % 64).

First, let’s see the code, and then we’ll add a bit of explanation.

(defn queens [^long dimension]
  {:pre [(<= 0 dimension 13)]}
  (let [add-queens (fn [qvs ^long row]
                     (for [qv qvs :let [conflicts (long (peek qv))]
                           col (range dimension)
                           :let [col (long col)
                                 rc (bit-or (bit-shift-left 1 col)
                                            (bit-shift-left 1 (+ row col dimension))
                                            (bit-shift-left 1 (- row col dimension)))]
                           :when (zero? (bit-and conflicts rc))]
                       (conj (pop qv) col (bit-or conflicts rc))))]
    
    (map pop (reduce add-queens [[0]] (range dimension)))))

In the queens function, we have a local rc that holds a long with three bits set corresponding to the column and two diagonals markers. The test for conflicts requires just a single bit-and calculation and a zero? test. We’re using reduce to drive the search, row by row, as it calls add-queens. The qvs “state” is a collection of partial assignments, where each assignment is a vector of queen columns plus an extra element, which is a long integer holding the board state for the current assignments. We can efficiently peek and pop the last element of the vector, making it a convenient way to carry extra bookkeeping data. On each assignment, we pop off the old board state, then conj the new queen column and the new board state. Partial solutions that cannot be extended safely are effectively dropped. The initial value of [[0]] is a collection of a single vector denoting the empty board with no conflicts. When we get to the reduce result, we need to pop off the bookkeeping data to return the desired final result. There are a couple of type hints and casts to let the code run with *unchecked-math* as a performance boost.

Although there’s a limit on the dimension, the queens function certainly works well for Eight Queens, which was our original target. It’s much faster than the simpler rosetta-queens mainly because it does less work, but also because the encoding allows for more efficient conflict checking.

If you read the Wikipedia article, you will find a link to a fast solution by Martin Richards (2009). (Credit is also given to Zongyan Qiu for publishing same solution in 2002.) After coming up with my solution, I went back to look at the Richards approach.

The clever part of the Richards algorithm is how it keeps track of diagonal conflicts by using bit-shifts. When a queen is placed in a column, it threatens diagonally the columns in the next row that are one less and one more. If you combine the diagonal conflicts for the assigned queens and shift once per row, you have all the conflicts for the next row. That means you need three integers to keep track of the current columns and each of the diagonals, which are designated “right” and “left” in the sense that they descend to the right or left of the position of a queen. Some bitwise logic reveals the open positions for a queen in the next row.

I implemented a reasonable facsimile of the Richards algorithm in Clojure, but it was about the same speed as my queens and somewhat more complicated. However, I could not help feeling that there must be a better way. I doubt Donald Knuth would approve, but I got a little carried away with some experiments focused on performance.

Perhaps I should be embarrassed by my fastest-queeens, but I’m also a little bit proud that it shows a pretty good performance improvement. There’s a lot of code to handle bit twiddling along the lines of the Richards approach. I’m basically encoding the Richards bookkeeping into a single long and shifting the bits as necessary. (If you’re thinking this guy should just give up and use C, you’re probably right!) I’m limiting my solutions to dimensions less than 15, so I can fit all the bookkeeping bits in one long. I’m not going to explain all the details. Tweet @miner if you have questions. Suffice it to say, it’s roughly twice as fast as my previous queens solution.

	
(defn fastest-queens [^long dimension]
  {:pre [(<= 0 dimension 14)]}
  (let [mask (dec (bit-shift-left 1 dimension))
        mask16 (bit-shift-left mask 16)
        mask32 (bit-shift-left mask 32)
        mask48 (bit-shift-left mask 48)

        shift-conflicts (fn [^long conflicts]
                          (let [rdiag (bit-and mask16 (unsigned-bit-shift-right conflicts 1))
                                ldiag (bit-and mask32 (bit-shift-left conflicts 1))
                                qcols (bit-and mask48 conflicts)]
                            (bit-or rdiag ldiag qcols
                                    (unsigned-bit-shift-right rdiag 16)
                                    (unsigned-bit-shift-right ldiag 32)
                                    (unsigned-bit-shift-right qcols 48))))
        
        add-queens
        (fn [qvs]
          (loop [qvs qvs xvs ()]
            (if-let [qv (first qvs)]
              (recur (rest qvs)
                     (let [^long conflicts (peek qv)]
                       (loop [vs xvs n (bit-and-not mask conflicts)]
                         (if (zero? n)
                           vs
                           (let [q (Long/numberOfTrailingZeros n)
                                 colmask (bit-shift-left 0x0001000100010001 q)]
                             (recur (conj vs (conj (pop qv) q
                                                   (shift-conflicts (bit-or conflicts colmask))))
                                    (bit-and-not n colmask)))))))
              
              xvs))) ]

    (mapv pop (nth (iterate add-queens [[0]]) dimension))))

Execution time from Criterium for the Eight Queens puzzle benchmark on my oldish iMac.

You can find my Queens project on GitHub.

Update: I added another implementation using Tarantella and blogged about it as Tarantella Queens.