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