如何编写正确的Shen程序解决八皇后问题？参考Prolog实现

以下是符合Shen逻辑编程范式的八皇后问题正确实现，核心思路与Prolog版本一致，利用全排列保证行列唯一性，再验证对角线约束：

(define queens
  (lambda (?N ?Solution)
    (<- (permutation (range 1 ?N) ?Solution)
        (safe ?Solution))))

(define permutation
  (lambda (?List ?Result)
    (<- (empty? ?List) (empty? ?Result))
    (<- (cons ?X ?Xs ?List)
        (remove ?X ?List ?Temp)
        (permutation ?Temp ?Ts)
        (cons ?X ?Ts ?Result))))

(define remove
  (lambda (?X ?List ?Result)
    (<- (cons ?X ?Xs ?List) (equal? ?Xs ?Result))
    (<- (cons ?Y ?Ys ?List)
        (not (equal? ?X ?Y))
        (remove ?X ?Ys ?R)
        (cons ?Y ?R ?Result))))

(define safe
  (lambda (?Queens)
    (<- (empty? ?Queens) true)
    (<- (cons ?Q ?Qs ?Queens)
        (safe ?Qs)
        (no-attack ?Q ?Qs 1))))

(define no-attack
  (lambda (?Q ?Queens ?Distance)
    (<- (empty? ?Queens) true)
    (<- (cons ?Q1 ?Qs ?Queens)
        (not (equal? (abs (- ?Q ?Q1)) ?Distance))
        (no-attack ?Q ?Qs (+ ?Distance 1)))))

(define eight-queens
  (lambda (?Solution)
    (<- (queens 8 ?Solution))))

代码说明 #

• queens 通用n皇后谓词：接受皇后数量?N和解列表?Solution，先通过permutation生成1到?N的全排列（确保每行每列仅一个皇后），再通过safe验证对角线安全性。
• permutation 与 remove：实现全排列生成，递归移除列表元素并构建所有可能的排列组合，逻辑与Prolog的排列谓词完全对应。
• safe 与 no-attack：safe递归遍历每个皇后，调用no-attack检查当前皇后与后续皇后的位置：?Distance代表行差，验证列差的绝对值不等于行差（避免对角线攻击）。

运行方式 #

• 获取单个解：在Shen环境中执行 (eight-queens ?S)，?S会绑定到一个合法的皇后列位置列表（索引对应行号）。
• 获取所有解：执行 (find-all ?S (eight-queens ?S) ?AllSolutions)，?AllSolutions将包含八皇后问题的全部92个合法解。

内容的提问来源于stack exchange，提问作者Czentovic