-1

プログラムは、8人の女王のすべての可能な結果を​​生成することです。データ構造として行番号を含むリストを使用します。しかし、それを実行すると、間違った結果が得られました。これが私のコードです：

(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

あなたのアプローチは複雑すぎると思います。あなたがする必要があるのは：

2つの基準に一致する次のクイーンの新しい行番号を見つけます：1）まだ含まれていない2）新しい行番号とすでに使用されている行番号の間の距離が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 件の結果、そのうちの 1 つが書籍のソリューションです

これはコードの一部を (わずかに) リファクタリングしたもので、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 に答える