The eight queens puzzle is about placing eight queens on a 8x8 chess board such that none of the queens share the same row, column, and diagonal. In fact there are more than one ways to place eight queens on a chess board without violating the rule. The puzzle can be generalized into a n-queens puzzle where the player is tasked to place n queens on a nxn chess board.

This post is about my attempt to solve the n-queens puzzle using Clojure. The classic approach to solve the puzzle is to use a technique called backtracking. In backtracking, the entire solution space for the puzzle is searched until all or some of the solutions are found. In The Algorithm Design Manual, Steve Skiena outlines a general form of the backtracking algorithm.

The idea behind the backtracking algorithm is to progressively generate candidates that will eventually make up a solution to the problem. In the context of eight-queens puzzle, the algorithm will place one queen at a time until all eight queens are placed. Each newly placed queen will satisfy the rule of the puzzle—no two queens share the same row, column, and diagonal.

(defn backtrack [n partial-soln]
  (if (= (count partial-soln) n)
    [partial-soln]
    (let [candidates (gen-candidates n partial-soln)]
      (mapcat #(backtrack n (conj partial-soln %)) candidates))))

(defn n-queens [n]
  (backtrack n []))

In the above snippet, two functions are defined. The backtrack function first checks the length of the partial solution. The partial solution contains placements of queens on the chess board. When there are placements for n queens, we know we have a single complete solution. However, if there are less than n queens placed, the algorithm will find all the suitable placements for the next queen while making sure the rule of the puzzle is enforced. That’s what gen-candidates does; it returns all the valid placements in the next row for a queen. For each of the valid placements, the backtrack function will append the placement to its partial solution, then it continues to find the next valid placement for the next queen by calling itself. Put it another way, the backtrack function places a queen in one of the placements returned by gen-candidates, so it is one step/queen closer to finding a complete solution of placing n queens on a nxn chess board. The crucial bit is that gen-candidates must return proper set of candidates.

(defn invalid?
  [[newq-row newq-col] [row col]]
  (cond
    (= row newq-row) true
    (= col newq-col) true
    (= (Math/abs (- row newq-row))
       (Math/abs (- col newq-col))) true
    :else false))

(defn validPlacements
  [placements new-pos]
  (let [result (filter (partial invalid? new-pos) placements)]
    (if (empty? result)
      true
      false)))

(defn gen-candidates [n placements]
  (let [[last-row last-col] (if (empty? placements)
                              (list -1 0)
                              (last placements))
         row  (inc last-row)
         cols (map #(list row %) (range n))]
    (filter #(validPlacements placements %) cols)))

The idea of gen-candidates is to first generate all possible placements for the next queen, then filter out the placements that will violate the placement rule—no two queens share the same row, column, and diagonal. The two functions, validPlacements and invalid? are used to enforce the rule of the puzzle so no queens can attack each other.

In total there are 92 possible ways to place eights queen on a chess board. You can find all the solutions returned by calling:

user=> (count (n-queens 8))
92

Due to readability and space, I will show the solutions for a smaller chess board. Here are the solutions for the four-queens puzzle:

user=> (n-queens 4)
([(0 1) (1 3) (2 0) (3 2)]
 [(0 2) (1 0) (2 3) (3 1)])

There are two solutions to place four queens on a 4x4 chess board. The return value is a list that contains vectors, in this case, there are two. Each vector holds the placements for the four queens. The placements are represented as tuples with the first element being the row, and the second element being the column (both start at 0).

And finally, here are the solutions for six-queens:

user=> (pprint (n-queens 6))
([(0 1) (1 3) (2 5) (3 0) (4 2) (5 4)]
 [(0 2) (1 5) (2 1) (3 4) (4 0) (5 3)]
 [(0 3) (1 0) (2 4) (3 1) (4 5) (5 2)]
 [(0 4) (1 2) (2 0) (3 5) (4 3) (5 1)])

There you have it. My attempt at the n-queens puzzle using clojure. I must admit the performance is not that great, but I think it is a decent start.