SICP lec6a : 流 I part2 - 八皇后 (回溯搜索)

何谓 八皇后问题

“如何能够在8×8的西洋棋棋盘上放置八个皇后，任两个皇后都不能处于同一条横行、纵行或斜线上。”

假定有一个 safe?的function，来判断在已经有放置一些皇后的时候，再放置下一个皇后是否安全。
(defn safe? [row col queens-position])。

为什么叫做"回溯搜索"，举下面4X4棋盘的例子
尝试路线：(1,x,x,x)->(1,1,x,x)(不行回到上一步)->(1,x,x,x)->(1,2,x,x)->(1,2,3,x)(有可能全部x位置都不行)，就会回到(1,2,x,x)再继续下去，归纳"尝试(成功)->尝试(成功)->尝试(失败，回上一步)"，最后可以得到正确答案。

这非常複杂，且这种複杂很难描述，因为太过于注意时序了，先...然后...一步一步前进。

跳脱时间的方法

(网路上抄的答案 kerker)

(defn safe?  "Check if queen in last row is safe"  [positions]  (let [[queen-pos & left] positions        k (count positions)        diags-up (map - left (range 1 (inc k)))        diags-down (map + left (range 1 (inc k)))]    (empty? (filter (partial = queen-pos) (concat diags-up diags-down left)))))

(defn queens [board-size]  ((fn queen-cols [k]     (if (zero? k)       (list empty-board)       (for [rest-of-queens (queen-cols (dec k))             new-row (range 1 (inc board-size))             :let [new-cols (cons new-row rest-of-queens)]             :when (safe? new-cols)]         new-cols)))  board-size))

可以看到 for当中的实作：
rest-of-queens -> k列前 所有可行的位置
new-row -> 新列的每一个element
:let ... :when -> 当通过safe?时 执行 (cons new-row rest-of-queens)

结论：
为何会比较容易，因为把所有的解当成一个整体的 "集合"，而不是随着 "时序的状态变化" 一个一个地找出的

问题：
流集合的方式确实比较简单，也容易理解，但是一次直接叫出整个列的element，会不会太耗记忆体，相较于传统的解法一个一个去分析，虽然时间较长，但比较不耗记忆体。

接下来的 lazy seq 就是要解决太耗记忆体的部分。