SICP 2.42八皇后。幫助檢查我的代碼有什麼問題？

Question

該程序是生成八個皇后的所有可能的結果。 我使用包含行號的列表作爲數據結構。 但是當我運行它時，我得到了錯誤的結果。 這是我的代碼：

(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)) 

Answer 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) 

Answer 2

我今天完成了在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) 
) 

返回。 。 （3 7 2 8 5 4 6） （3 7 2 8 6 4 1 5） 。 。

92的結果，其中一個是在書中

這裏的解決方案是你的代碼的一部分（略）重構，我擺脫了我 - 刪除的，並使用一個讓*。 我不會重構整個事情，但我至少試圖在變量名稱中添加含義。 這些變化是有所加快： （也加入了一些評論）

;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))) 
. 
. 
. 

所以，我想我的，刪除您使用的可能是錯誤的。

現在，你的變量的名稱不是很有代表性，所以它會增加一個已經很混亂的代碼（這個練習或者你的作者沒有意思）。