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.
On Sun, Feb 8, 2009 at 7:56 PM, Jeffrey Straszheim <
[email protected]> wrote:
> Perhaps you are forcing a very long lazy list?
>
> Try (.printStackTrace *e)
>
>
> On Sun, Feb 8, 2009 at 9:41 AM, jodocus <[email protected]> wrote:
>
>>
>> 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 <http://en.wikipedia.org/wiki/%0A8_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)
>>
>> >>
>>
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
