Depth-first search in Clojure (`tree-seq`)

Step-by-step development of a depth-first search, using tree-seq, to solve a classic puzzle.

Author

Affiliation

Harold

TechAscent

Published

August 11, 2025

Keywords

tree-seq, puzzle

A classic puzzle involves placing eight queens on a chessboard so that no two are attacking each other.

Today, we search out such arrangements, in Clojure.

Since no solution has two queens on the same rank, a nice way to represent the board with data is as a vector of numbers, each element of the vector a column index for the queen on that rank.

For example, the vector [0 2] would be a board with two queens, one in the corner and another a knight’s move away.

(def board [0 2])

We can visualize boards by converting these vectors into so-called FEN strings, which can be converted into images by a web service provided by the caring strangers at chessboardimage.com.

First, we obtain the elements of the FEN string as a sequence.

(for [i board] (str i "q" (- 7 i)))

("0q7" "2q5")

FEN strings do not allow zeros (I do not make the rules).

(for [i board] (.replace (str i "q" (- 7 i)) "0" ""))

("q7" "2q5")

Each rank is delimited with a slash.

(->> (for [i board] (.replace (str i "q" (- 7 i)) "0" ""))
     (clojure.string/join "/"))

"q7/2q5"

That goes straight into the chessboardimage.com URL

(->> (for [i board] (.replace (str i "q" (- 7 i)) "0" ""))
     (clojure.string/join "/")
     (format "https://chessboardimage.com/%s.png"))

"https://chessboardimage.com/q7/2q5.png"

That is the body of a function that converts a board into an image

(defn board->image
  [board]
  (->> (for [i board] (.replace (str i "q" (- 7 i)) "0" ""))
       (clojure.string/join "/")
       (format "https://chessboardimage.com/%s.png")))

To solve the puzzle, we build a tree of candidate solution boards, the children of each node being boards with a new queen added on the next rank to each square not under attack.

To find the squares under attack, we begin by computing the board’s ranks.

(map-indexed vector board)

([0 0] [1 2])

Each queen attacks up to three squares on the next rank, so for each slope m in -1, 0, 1 and each queen’s rank and index, we produce three indexes under attack (y=mx+b).

(for [m [-1 0 1]
      [rank i] (map-indexed vector board)]
  (+ i (* m (- (count board) rank))))

(-2 1 0 2 2 3)

To compute the candidate squares, we take the set of valid indexes and remove those under attack.

(->> (for [m [-1 0 1]
           [rank i] (map-indexed vector board)]
       (+ i (* m (- (count board) rank))))
     (apply disj (set (range 8))))

#{7 4 6 5}

From those we produce a sequence of child boards.

(->> (for [m [-1 0 1]
           [rank i] (map-indexed vector board)]
       (+ i (* m (- (count board) rank))))
     (apply disj (set (range 8)))
     (map #(conj board %)))

([0 2 7] [0 2 4] [0 2 6] [0 2 5])

That is the body of a function that takes a board, and produces child boards in the tree of candidate solutions.

(defn board->children
  [board]
  (->> (for [m [-1 0 1]
             [rank i] (map-indexed vector board)]
         (+ i (* m (- (count board) rank))))
       (apply disj (set (range 8)))
       (map #(conj board %))))

We can enumerate all candidate boards with Clojure’s tree-seq; a function of three arguments, the first is a predicate that is true for nodes with children.

In our case, we keep adding queens as long as a board has fewer than eight queens.

(def boards (tree-seq #(< (count %) 8) ... ...))

The second argument to tree-seq is a function that given a node, produces a sequence of children.

We just wrote that function (board->children).

(def boards (tree-seq #(< (count %) 8) board->children ...))

The third argument to tree-seq is the root of the tree, an empty board [] will do.

(def boards (tree-seq #(< (count %) 8) board->children []))

The solutions to the puzzle are those boards with 8 queens on them.

(def solutions (filter #(= (count %) 8) boards))

Of which, there are this many…

(count solutions)

The forty-second such solution

(nth solutions 42)

[3 0 4 7 1 6 2 5]

As an image

(board->image (nth solutions 42))

"https://chessboardimage.com/3q4/q7/4q3/7q/1q6/6q1/2q5/5q2.png"

🙇

source: src/clojure/tree_seq/depth_first_search.clj