Stack overflow problem

[jodocus]

When I learn a new language, one of the programs I like to write as an
excercise is the n-queens problem (http://en.wikipedia.org/wiki/
8_queens). I wrote the program below which runs correctly. Using depth-
first search, I have used it to find the solutions for board sizes up
to 11 (after which it begins taking a lot of time).

But when I use breadth-first search it gives a stack overflow error at
boardsize 7. All recursive calls in the code are done using recur at
tail positions, and it is not clear to me what could otherwise cause
this. Does anyone have a suggestion how to track down the cause of
this stack overflow?

--------------------------------- code ----------------------------
(def dim 6)
(def numsqrs (* dim dim))
(def queen \*)
(def empty-sqr \.)

;; a "state" in this program is nothing more
;; than a list of positions on the board

;; returns true when placing a queen on both p1 and p2 is disallowed
(defn conflict? [p1 p2]
(let [x1 (rem p1 dim)
x2 (rem p2 dim)
y1 (quot p1 dim)
y2 (quot p2 dim)]
(or
(== x1 x2)
(== y1 y2)
;; diagonals
(let [dx (- x2 x1)
dy (- y2 y1)]
(or (== dx dy)
(== (- dx) dy))))))

(defn remove-conflicted [p ps]
(remove #(conflict? p %) ps))

;; returns a list of all squares where a queen can be placed in given
state
(defn get-safe-squares [state]
(loop [safe (range (inc (first state)) numsqrs), s state]
(when-not (empty? safe)
(if-not (empty? s)
(recur (remove-conflicted (first s) safe) (rest s))
safe))))

;; given a state with n queens, returns all possible states with n+1
queens
(defn children [state]
(if (empty? state)
(map #(list %) (range numsqrs))
(when (< (count state) dim)
(map #(conj state %) (get-safe-squares state)))))

(defn add-children [searchtype statelist]
(let [c (children (first statelist))
s (rest statelist)]
(cond
(= searchtype :breadth-first) (concat s c)
(= searchtype :depth-first) (concat c s))))

(defn search
([searchtype] (search searchtype (children ()) 0 0))
([searchtype statelist n found]
(if-not (empty? statelist)
(let [s (first statelist)
is-solution (>= (count s) dim)
fnd (if is-solution (inc found) found)]
(when is-solution
(println (format "Solution: %d, queens at: %s, searched: %d" fnd
s (inc n))))
; (print-state s))
(recur searchtype (add-children searchtype statelist) (inc n)
fnd))
{:searched n :found found})))

(search :breadth-first)

[Jeffrey Straszheim]

Perhaps you are forcing a very long lazy list?

Try (.printStackTrace *e)

[Jeffrey Straszheim]

In fact, try this:

(defn add-children [searchtype statelist]
 (let [c (children (first statelist))
               s (rest statelist)]
       (cond

        (= searchtype :breadth-first) (doall (concat s c))
        (= searchtype :depth-first) (doall (concat c s)))))


The doall forces the lists then and there.

[Jeffrey Straszheim]

Did this work for you?  Do you understand what the problem was?