-1

该程序将生成八个皇后的所有可能结果。我使用包含行号的列表作为数据结构。但是当我运行它时，我得到了错误的结果。这是我的代码：

(define (queens board-size)
  (define (safe? k position)
    (define (iter last-element front-lst col-num k)
      (define (ok? l-e car-lst)
    (and (not (= l-e car-lst))
         (not (= (abs (- l-e car-lst)) (abs (- k col-num))))))
      (if (null? front-lst)
      true
      (and (ok? last-element (car front-lst))
           (iter last-element (cdr front-lst) (++ col-num) k))))
    (let ((l-e (car (my-reverse position)))
      (f-l (my-remove (car (my-reverse position)) position)))
      (iter l-e f-l 1 k)))

  (define empty-board nil)

  (define (adjoin-position new-row k rest-of-queens)
    (append rest-of-queens (list new-row)))

  (define (queen-cols k)
    (if (= k 0)
    (list empty-board)
    (filter
     (lambda (positions) (safe? k positions))
     (my-flatmap
      (lambda (rest-of-queens)
        (map (lambda (new-row)
           (adjoin-position new-row k rest-of-queens))
         (enumerate-interval 1 board-size)))
      (queen-cols (-- k))))))
  (queen-cols board-size))
4

2 回答 2

1

我怀疑你的方法太复杂了。你需要做的是：

为下一个皇后找到一个符合两个条件的新行号：1）它尚未包含 2）新行号与任何已使用的行号之间的距离不等于两行的距离。

递归执行此操作。

我的 CL 解决方案供参考：

(defun fits (p list)
  (and (not (member p list))
       (loop for i in list as j from 1
            never (eql (abs (- p i)) j))))

(defun backtrack (list)
  (if (eql (length list) 8)
      (print list)
      (loop for i from 1 to 8
         when (fits i list)
           do (backtrack (cons i list)))))

运行

(backtrack nil)
于 2012-09-12T09:52:51.877 回答
1

我今天刚刚在 SICP 中完成了这个问题，所以我会尝试在这里提供帮助：

我用这个 my-remove 测试了你的代码：

(define (my-remove num num-list)
    (cond   ((null? num-list) nil)
            ((= num (car num-list)) (cdr num-list))
            (else (cons (car num-list) (my-remove num (cdr num-list))))))

测试：

(let ((result (queens 8)))
(display (length result))(newline)
(map (lambda (possible-solution) (display possible-solution)(newline)) result)
)

返回 92 。. (3 7 2 8 5 1 4 6) (3 7 2 8 6 4 1 5)。.

92个结果，其中一个是书中的解决方案

这是您的代码的一部分（稍微）重构，我摆脱了 my-remove，并使用了 let*。我不打算重构整个事情，但我至少尝试在变量名中添加含义。有了这些变化，速度更快了：（还添加了一些评论）

;no major refactoring, essentially removed my-remove and some refactors
(define (queens board-size)
  (define (safe? k position)
    (define (iter last-element front-lst col-num k)
        ;what's ok?
      (define (ok? l-e car-lst)
            (and (not (= l-e car-lst))
                (not (= (abs (- l-e car-lst)) (abs (- k col-num))))))
      (if (null? front-lst)
      true
      (and (ok? last-element (car front-lst))
           (iter last-element (cdr front-lst) (++ col-num) k))))
    ;queens means a list of rows, each representing a queen position
    ;that is, when queens[col] = row  that means there's a queen in row 'row and 
    ;column 'col

    ;reimplementing removing the queen, and the let turned to let*
    (let* ((reverse-column-queens (my-reverse position))
           (last-queen (car reverse-column-queens))
        ;remove that queen from the list
        ;btw 'position is actually 'positions
        (all-other-queens (my-reverse (cdr reverse-column-queens))))
      (iter last-queen all-other-queens 1 k)))
.
.
.

所以，我猜你使用的 my-remove 可能是错误的。

现在，您的变量名称不是很具有描述性，因此它会添加到已经令人困惑的代码中（无意冒犯本练习的作者或您）。

于 2012-09-12T17:25:15.937 回答