SICP自留地: January, 2008

<< First < Previous Next > Last >>

January 02

sicp 2.43

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

(define empty-board (list))
(define (adjoin-position new-row k rest-of-queens)
(cons (list new-row k) rest-of-queens))
(define (safe? k positions)
(let ((new-row (car (car positions)))
        (rest-position (cdr positions)))
    (and (not (have-row? new-row rest-position))
         (not (diagonal? new-row k rest-position))
         )))
(define (have-row? new-row rest-position)
(cond ((null? rest-position) #f)
        ((= new-row (car (car rest-position))) #t)
        (else (have-row? new-row (cdr rest-position)))
        ))
(define (diagonal? new-row k rest-position) ;could split it into modules here

(cond ((null? rest-position) #f)
        ((or (= (- new-row (car (car rest-position)))
                (- k (car (cdr (car rest-position)))))
             (= (- new-row (car (car rest-position)))
                (- (car (cdr (car rest-position))) k)))
         #t)
        (else (diagonal? new-row k (cdr rest-position)))
        ))

;code provided in the sicp textbook start here
(define (fold-left op initial sequence)
(define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
(iter initial sequence))
(define (enumerate-interval low high)
(if (> low high)
      (list)
      (cons low (enumerate-interval (+ low 1) high))))
(define (remove item sequence)
(filter (lambda (x) (not (= x item)))
          sequence))
(define (filter predicate sequence)
(cond ((null? sequence) (list))
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))
(define (flatmap proc seq)
(accumulate append (list) (map proc seq)))
(define (accumulate op initial sequence)
(if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

Blog

sicp 2.43