Stackoverflow when calling sol-count on 10 (N-queens program)

Question

So this is my first time programming in clojure and I am running into some issues with stackoverflow with my program. This program basically tries to find all the possible solutions to the N-queens problem

http://en.wikipedia.org/wiki/Eight_queens_puzzle

When I call sol-count (finds number of solutions for a given N) on 10 or higher I get a stack overflow

(defn qextends?
  "Returns true if a queen at rank extends partial-sol."
  [partial-sol rank]
  (if (>= (count partial-sol) 1)
    (and
      (not= (first partial-sol) (- rank (count partial-sol)))
      (not= (first partial-sol) (+ rank (count partial-sol)))
      (not= (first partial-sol) rank)
      (qextends? (rest partial-sol) rank))
    true)
  )

(defn qextend-helper [n x partial-sol partial-sol-list]
  (if (<= x n)
    (if (qextends? partial-sol x)
      (qextend-helper n (inc x) partial-sol (conj partial-sol-list (conj partial-sol x)))
      (qextend-helper n (inc x) partial-sol partial-sol-list)
    )
  partial-sol-list)
  )


(defn qextend
  "Given a vector *partial-sol-list* of all partial solutions of length k,
  returns a vector of all partial solutions of length k + 1.
  "
  [n partial-sol-list]
  (if (>= (count partial-sol-list) 1)
    (vec (concat (qextend-helper n 1 (first partial-sol-list) [])
      (qextend n (rest partial-sol-list))))
    nil))

(defn sol-count-helper
  [n x partial-sol-list]
  (if (<= x (- n 1))
    (sol-count-helper n (+ 1 x) (qextend n partial-sol-list))
    (qextend n partial-sol-list))
  )

(defn sol-count
  "Returns the total number of n-queens solutions on an n x n board."
  [n]
  (count (sol-count-helper n 1 [[]]))
  )

Answer 1

Completing dizzystar's answer:

Most of your recursions can be recurred: You can put recur inside if, and hence under and and or, macros which expand to if forms. For example ...

(defn qextend-helper [n x partial-sol partial-sol-list]
  (if (<= x n)
    (if (qextends? partial-sol x)
      (recur n (inc x) partial-sol (conj partial-sol-list (conj partial-sol x)))
      (recur n (inc x) partial-sol partial-sol-list))
    partial-sol-list)
  )

But the recursive call in qextend:

(vec (concat ( ...)
             (qextend n (rest partial-sol-list))))

... can't be dealt with by recur, since it is buried in function calls, to concat and vec.

You can solve this problem by returning a lazy sequence, so making the partial-sol-list argument lazy:

• get rid of vec - return the sequence - and
• replace concat with lazy-cat.

The resulting function is

(defn qextend [n partial-sol-list]
  (if (seq partial-sol-list)
    (lazy-cat (qextend-helper n 1 (first partial-sol-list) [])
            (qextend n (rest partial-sol-list)))
    nil))

You also have to avoid counting (and hence realizing) the lazy sequence: so useseq instead to test whether there is anything in partial-sol-list.

It works!

=> (sol-count 11)
2680