在10上调用sol-count时的Stackoverflow(N-queens程序)

Question

所以这是我第一次使用clojure进行编程,而且我的程序遇到了stackoverflow的一些问题.该程序基本上试图找到N-queens问题的所有可能解决方案

http://en.wikipedia.org/wiki/Eight_queens_puzzle

当我在10或更高时调用sol-count(找到给定N的解的数量)时,我得到堆栈溢出

(defn qextends?
  "Returns true if a queen at rank extends partial-sol."
  [partial-sol rank]
  (if (>= (count partial-sol) 1)
    (and
      (not= (first partial-sol) (- rank (count partial-sol)))
      (not= (first partial-sol) (+ rank (count partial-sol)))
      (not= (first partial-sol) rank)
      (qextends? (rest partial-sol) rank))
    true)
  )

(defn qextend-helper [n x partial-sol partial-sol-list]
  (if (<= x n)
    (if (qextends? partial-sol x)
      (qextend-helper n (inc x) partial-sol (conj partial-sol-list (conj partial-sol x)))
      (qextend-helper n (inc x) partial-sol partial-sol-list)
    )
  partial-sol-list)
  )


(defn qextend
  "Given a vector *partial-sol-list* of all partial solutions of length k,
  returns a vector of all partial solutions of length k + 1.
  "
  [n partial-sol-list]
  (if (>= (count partial-sol-list) 1)
    (vec (concat (qextend-helper n 1 (first partial-sol-list) [])
      (qextend n (rest partial-sol-list))))
    nil))

(defn sol-count-helper
  [n x partial-sol-list]
  (if (<= x (- n 1))
    (sol-count-helper n (+ 1 x) (qextend n partial-sol-list))
    (qextend n partial-sol-list))
  )

(defn sol-count
  "Returns the total number of n-queens solutions on an n x n board."
  [n]
  (count (sol-count-helper n 1 [[]]))
  )

Answer 1

完成dizzystar的答案:

大部分的递归可recur红:你可以把recur里面if,因此在and和or,宏其扩展到if形式.例如 ...

(defn qextend-helper [n x partial-sol partial-sol-list]
  (if (<= x n)
    (if (qextends? partial-sol x)
      (recur n (inc x) partial-sol (conj partial-sol-list (conj partial-sol x)))
      (recur n (inc x) partial-sol partial-sol-list))
    partial-sol-list)
  )

但递归调用qextend:

(vec (concat ( ...)
             (qextend n (rest partial-sol-list))))

......不能处理的recur,因为它是埋在函数调用,以concat和vec.

你可以通过返回一个懒惰的序列来解决这个问题,所以让partial-sol-list参数变得懒惰:

• 摆脱vec- 返回序列 - 和
• 替换concat为lazy-cat.

由此产生的功能是

(defn qextend [n partial-sol-list]
  (if (seq partial-sol-list)
    (lazy-cat (qextend-helper n 1 (first partial-sol-list) [])
            (qextend n (rest partial-sol-list)))
    nil))

你还必须避免count(并因此实现)懒惰的序列:所以seq改用它来测试是否有任何东西partial-sol-list.

有用!

=> (sol-count 11)
2680