Did this work for you? Do you understand what the problem was? On Sun, Feb 8, 2009 at 8:06 PM, Jeffrey Straszheim < straszheimjeff...@gmail.com> wrote:
> 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 < > straszheimjeff...@gmail.com> wrote: > >> Perhaps you are forcing a very long lazy list? >> >> Try (.printStackTrace *e) >> >> >> On Sun, Feb 8, 2009 at 9:41 AM, jodocus <rjek...@gmail.com> 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 clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
