3

所以这是我第一次在 clojure 中编程，我的程序遇到了一些 stackoverflow 问题。该程序基本上试图找到 N 皇后问题的所有可能解决方案

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 [[]]))
  )
4

2 回答 2

5

完成头晕星的回答：

您的大多数递归都可能是recur红色的：您可以在recur内部if，因此在andandor下放置扩展为表单的宏。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，因为它被隐藏在函数调用中， toconcat和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))

您还必须避免counting （并因此实现）惰性序列：因此请改用seq测试partial-sol-list.

有用！

=> (sol-count 11)
2680
于 2014-03-09T12:34:12.523 回答
3

首先，Clojure 不像其他 lisp 那样具有 TCO。为了缓解这种情况，Clojure 提供了loop 和 recur。在 Clojure 和其他 lisps 中，您通常没有显式返回，相反，重点是返回值。

我修复了 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 或其他构造，我鼓励您在解决此问题后研究其他选项。

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

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

最后，这种缩进风格和将括号放在自己的行上并不能提高可读性。：

      (qextend-helper n (inc x) partial-sol partial-sol-list)
    )
  partial-sol-list)
  )
于 2014-03-09T08:56:35.070 回答