Mark Engelberg recently announced an update to his Tarantella library for Clojure. Tarantella is an implementation of Knuth’s Dancing Links algorithm for solving exact cover problems. Mark gave an excellent talk at the 2017 Clojure Conj entitled “Solving Problems Declaratively” which explains the algorithm and demonstrates how Tarantella works.
Tarantella starts with a matrix of constraints. Each row in the matrix has certain columns set (marked 1) for a corresponding constraint. Tarantella searches for a covering set of rows such that each column is set once in the solution set. For convenience, the constraint matrix can be specified as a set of marked columns rather than listing all the ones and zeroes explicitly.
In my previous Eight Queens implementation, I used the terms “row” and “column” to label the positions on the board. Chess players would probably prefer “rank” and “file”. To avoid confusion, in this post I will refer to the positions as X-Y coordinates on an N-by-N board. See my blog post for an explanation of how the N-Queens problem is essentially concerned with finding unique positions in terms of X, Y, and the two diagonals.
To work with Tarantella, we need to encode our constraints for the positions of the queens
as Tarantella columns. X and Y each have
N possible values. The diagonal constraints
correspond to the sums and differences of X and Y at each square. Thus, there are
possible values for each diagonal. We have to designate each constraint as a separate
column. That makes a total of
6N-2 columns. It’s convenient to encode X as the first N
N-1), and Y as the next N columns (
2N-1). These constraint
columns must be set exactly once to get unique placements in the X and Y coordinates. Each
diagonal constraint is assigned sequentially to an additional
2N-1 columns. Note that the
diagnonal constraints are declared as optionals for Tarantella, which means they can be set
once or not at all for a solution.
The solutions returned by
dancing-links are row numbers from the original constraints. We
can convert back to Y coordinates using
(rem ROW N). The final result follows the
convention used in my other N-Queens solutions. Each solution is a vector of Y coordinates
for the queens. The X coordinates are implied by the index order.
(require '[tarantella.core :as t]) (defn queens-constraints [n] (for [x (range n) y (range n)] [x (+ n y) (+ n n x y) (+ (* 5 n) (- x y 2))])) ;; The rows in a solution aren't guaranteed in any particular order so we ;; need to sort first, then decode queen placements from the row numbers. (defn solve-queens [n] (map (fn [sol] (mapv #(rem % n) (sort sol))) (t/dancing-links (queens-constraints n) :optional-columns (range (* 2 n) (- (* 6 n) 2)))))
Execution time from Criterium for the Eight Queens puzzle benchmark on my oldish iMac.
|(solve-queens 8)||931.9 µs|
|(queens 8)||928.8 µs|
|(fastest-queens 8)||383.0 µs|
|(solve-queens 13)||1.5 s|
|(queens 13)||2.3 s|
|(fastest-queens 13)||0.9 s|
|(solve-queens 14)||9.4 s|
|(fastest-queens 14)||14.7 s|
For Eight Queens, the Tarantella solution is on par with my previous
which I thought was moderately clever. The Tarentalla approach is also much simpler code
than my bit-twiddling
fastest-queens. I highly recommend considering Tarantella for your
future puzzle solving needs. It’s nice to have someone else do the hard work for you.
Update: My original benchmarking was for N=8. I added some timings for larger values of N. On my machine, at N=14, the Tarantella version is the clear performance winner.
You can find my updated Queens sample code on GitHub.