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

Answer 2

For starters, Clojure does not have TCO like other lisps. To mitigate this, Clojure offers loop and recur. In Clojure and other lisps, you generally do not have explicit returns, instead, the focus is on returning values.

I fixed up the qextend-helper to give you a start. I tested a few of your answers against the snippet that I replaced here, and they all resolve to the same solution. You still can't go past 10 even with this snippet inside of it, but if you continue to remove all the tail call recursions, you should be able to get past the stackoverflow errors:

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

I should point out also that the above isn't great Clojure either. There are many other solutions online that are less LOC and more Clojure-y, but since you are starting down this route, I am simply attempting to encourage you to remove the errors that you are running into. In this case, removing the tail-calls is a good place to start. With that said, there is nothing that would stop you from using for or other constructs and I encourage you to look into other options after you solved this.

When using recur, resist the temptation to put recur at the end of a function to simulate TCO:

(defn my-funct [x]
      .....
      (recur x))

Finally, this indention style and putting parens on their own lines does not improve readability.:

      (qextend-helper n (inc x) partial-sol partial-sol-list)
    )
  partial-sol-list)
  )