调用sol-count on 10 (N-queens程序)时发生Stackoverflow

Question

所以这是我第一次在clojure编程，我遇到了一些问题与stackoverflow与我的程序。这个程序基本上试图找到n皇后问题的所有可能的解

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

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

(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 -返回序列-和
• 用lazy-cat代替concat

结果函数是

(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

Answer 2

对于初学者来说，Clojure不像其他lisp那样有TCO。为了缓解这个问题，Clojure提供了循环和循环。在Clojure和其他lisp语言中，通常没有显式返回，相反，重点是返回值。

我修复了qextend-helper，为您提供了一个开始。我将您的一些答案与我在这里替换的代码片段进行了测试，它们都解析为相同的解决方案。即使有了这个代码片段，仍然不能超过10，但是如果继续删除所有的尾部调用递归，应该能够超过stackoverflow错误:

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

我还应该指出，上面的Clojure也不是很好。网上还有许多其他的解决方案，它们较少使用LOC，而更多使用Clojure-y，但是由于您正在沿着这条路线开始，所以我只是试图鼓励您删除遇到的错误。在这种情况下，消除尾部呼叫是一个很好的开始。话虽如此，没有什么能阻止您使用for或其他结构，我鼓励您在解决这个问题后寻找其他选项。

当使用recr时，请抵制将recr放在函数末尾以模拟TCO的诱惑:

(defn my-funct [x]
      .....
      (recur x))

最后，这种缩进样式和将父行放在自己的行上并不能提高可读性。:

      (qextend-helper n (inc x) partial-sol partial-sol-list)
    )
  partial-sol-list)
  )