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 -~----------~----~----~----~------~----~------~--~---
