Eight queens puzzle

Question

Problem

In the famous eight queens puzzle, one must place eight queens on a chessboard without letting any queen threaten any other queen. There are 92 (or 12, depending on how you count) solutions to the original puzzle, but it can also be generalized to smaller or larger boards.

Solution

My strategy is pretty similar to the one used in SICP; the fill function calls itself recursively to find all the ways to place queens through (dec row) in an \$n \times n\$ board, then uses safe? to return all the ways to place queens through row.

#!/usr/bin/env boot

(defn threat? [queen piece]
  (let [[r1 c1] queen
        [r2 c2] piece]
    (or (= r1 r2)
        (= c1 c2)
        (= (Math/abs (- r2 r1))
           (Math/abs (- c2 c1))))))

(defn safe? [board pos]
  (not-any? #(threat? % pos) board))

(defn fill [n row]
  (if (zero? row)
    (for [col (range n)]
      #{[row col]})
    (for [board (fill n (dec row))
          col (range n)
          :let [pos [row col]]
          :when (safe? board pos)]
      (conj board pos))))

(defn queens [n]
  (fill n (dec n)))

(require '[boot.cli :as cli])

(cli/defclifn -main
  "Print all the ways to place N queens on an NxN chessboard so that no two
  queens threaten each other. Each solution is represented as a set of positions
  of queens, where a position is represented as a vector of two integers."
  [n number NUM int "The number of rows, columns, and queens."]
  (run! prn (queens (or number 8))))

Examples

You'll need to install Boot and save the above script as queens; then you can run it directly:

$ chmod +x queens
$ ./queens -n1
#{[0 0]}
$ ./queens -n2
$ ./queens -n3
$ ./queens -n4
#{[1 3] [2 0] [3 2] [0 1]}
#{[1 0] [2 3] [0 2] [3 1]}
$ ./queens -n5
#{[4 3] [0 0] [2 4] [3 1] [1 2]}
#{[0 0] [3 4] [4 2] [1 3] [2 1]}
#{[1 3] [2 0] [4 4] [3 2] [0 1]}
#{[4 3] [2 2] [3 0] [1 4] [0 1]}
#{[1 0] [2 3] [0 2] [3 1] [4 4]}
#{[3 3] [1 4] [0 2] [2 1] [4 0]}
#{[2 2] [1 0] [3 4] [4 1] [0 3]}
#{[1 1] [0 3] [2 4] [3 2] [4 0]}
#{[2 3] [1 1] [4 2] [3 0] [0 4]}
#{[3 3] [4 1] [2 0] [0 4] [1 2]}
$ ./queens -n6
#{[2 5] [5 4] [4 2] [3 0] [1 3] [0 1]}
#{[3 4] [5 3] [1 5] [0 2] [2 1] [4 0]}
#{[1 0] [5 2] [0 3] [2 4] [4 5] [3 1]}
#{[4 3] [5 1] [2 0] [0 4] [1 2] [3 5]}
$ ./queens | wc -l
92

Questions

• Can any of my functions be further decomposed?
• Is there a more elegant way to solve this problem?
• Are there any other improvements that should be made?

Answer 1

I think this is about as good as it can get. threat? can be improved through destructuring:

(defn threat? [[queen-r queen-c] [piece-r piece-c]]
  (or (= queen-r piece-r)
      (= queen-c piece-c)
      (= (Math/abs (- queen-r piece-r))
         (Math/abs (- queen-c piece-c)))))

You could re-write fill to be another arity of queens itself, but it depends on how you'd like your code to be used.

I love the for-loop in fill!