Hatena::Groupsicp

SICP in the blanket

2008-09-26

2章 - N Queen

01:54 | はてなブックマーク - 2章 - N Queen - SICP in the blanket 2章 - N Queen - SICP in the blanket のブックマークコメント

ex2.42

一応貼っとく

(define empty-board '())

(define (enumerate-interval a b)
  (if (> a b) '()
      (cons a (enumerate-interval (+ a 1) b))))

(define (safe? k positions)
  (define (collide x y)
    (let ((c1 (car x)) (r1 (cdr x))
          (c2 (car y)) (r2 (cdr y)))
      (or (= c1 c2) (= r1 r2)
          (= (+ c1 r1) (+ c2 r2))
          (= (- c1 r1) (- c2 r2)))))
  (let ((kth (car positions)))
    (accumulate (lambda (x y) (and x y))
                #t
                (map (lambda (x) (not (collide kth x)))
                     (cdr positions)))))

(define (adjoin-position r c qs)
  (cons (cons c r) qs))

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

ex2.43

漸化式は 2.42のが

T(n) = T(n-1) + A*n*q(n-1) + B

で2.43のが

T'(n) = n*T'(n-1) + A*n*q(n-1) + B

ぐらいか? (q(n)はn-queenの解の数, A,Bは適当な定数)

なんか n が十分でかくなると n! 倍ぐらい差が出そうな感じ?

MattinglyMattingly2012/01/09 19:57Good to see real expertise on display. Your cotnrbiution is most welcome.

exjurlpgksoexjurlpgkso2012/01/10 17:23LtAXNu <a href="http://qwymdffdvjgu.com/">qwymdffdvjgu</a>

igtnwvigtnwv2012/01/15 01:29lgrZ4A , [url=http://dgncekoxiect.com/]dgncekoxiect[/url], [link=http://kgqqnwfzdjcy.com/]kgqqnwfzdjcy[/link], http://jtteuxkxmnoa.com/

トラックバック - http://sicp.g.hatena.ne.jp/blanketsky/20080926