宿題

昨晩はダメダメでしたが、寝て起きて紙に書きつつ云々でなんとなく動きそうな気がしてきた。new-row をアタマにつけるかシリにつけるかでナニ。

とりあえず

new-row をアタマに付けたら楽そうなんだけど、safe? も adjoin-position も引数を無視する作りになりそうなカンジ。メンドいけど指定されてる引数を使う形で作ってみるか。
なんか前ヤッた時にも同じ間違いをした記憶がありますが、list されるのをスルーして

(define empty-board '(()))

ってヤッててナニ。一応

gosh> (length (queens 8))
92
gosh>

ってなってるので正解なんだろうと思います。以下が実装。

;; filter
(define (filter p s)
  (cond ((null? s) '())
	((p (car s))
	 (cons (car s)
	       (filter p (cdr s))))
	(else
	 (filter p (cdr s)))))
;; accumulate
(define (accumulate op init s)
  (if (null? s)
      init
      (op (car s)
	  (accumulate op init (cdr s)))))
;; flatmap
(define (flatmap p s)
  (accumulate append '() (map p s)))
;; enumerate-interval
(define (enumerate-interval l h)
  (if (> l h)
      '()
      (cons l (enumerate-interval (+ l 1) h))))

;; empty-board
(define empty-board '())
;; safe?
(define (safe? row l)
  (define (get-new-row l)
    (if (null? (cdr l))
	(car l)
	(get-new-row (cdr l))))
  (let f ((r 1) (l l) (new-row (get-new-row l)))
    (cond ((= r row) #t)
	  ((= new-row (car l)) #f)
	  ((= new-row (+ (car l) (- row r))) #f)
	  ((= new-row (- (car l) (- row r))) #f)
	  (else
	   (f (+ r 1) (cdr l) new-row)))))
;; adjoin-position
(define (adjoin-position new-row k rest-of-queens)
  (append rest-of-queens (cons new-row '())))

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
	(list empty-board)
	(filter
	 (lambda (positions) (safe? k positions))
	 (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 1))))))
  (queen-cols board-size))

で、もう一つ new-row をアタマに付けてく実装を考えてみる事に。とりあえずここでエントリ投入。

もうひとつの

実装。safe? と adjoin-position が違うだけです。以下?

(define (safe? row l)
  (let f ((r 1) (top (car l)) (rest (cdr l)))
    (cond ((null? rest) #t)
	  ((= top (car rest)) #f)
	  ((= top (+ (car rest) r)) #f)
	  ((= top (- (car rest) r)) #f)
	  (else
	   (f (+ r 1) top (cdr rest))))))

;; adjoin-position
(define (adjoin-position new-row k rest-of-queens)
  (cons new-row rest-of-queens))

実行してみたら偉く気持ちの悪いリストが出てきた。length は同じ数なので合ってると思いたいんですが。。
余裕があれば何故にこんな出力になるのか、を検討したいですが、もう昼だな。

gosh> (queens 8)
((4 2 7 3 6 8 5 . #0=(1)) (5 2 4 7 3 8 6 . #0#) ;; 以下略

問題 2.43

以下だと

(flatmap
  (lambda (new-row)
    (map (lambda (rest-of-queens)
           (adjoin-position new-row k rest-of-queens))
         (queen-cols (- k 1))))
  (enumerate-interval 1 board-size))

queen-cols 手続きが board-size 回呼ばれる事になるんかな。2.42 が T だと T の二乗って事になるのかどうか。

む

T の 2 乗じゃなくて T の T 乗とかってオチ?
上記の形になってると、数えあげる度に (queen-cols (- k 1)) する形になるので効率が非常に悪いです。