SICP 2.2 exercises cont. 2

2.42

(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)
  (display rest-of-queens)
  (newline)
  (append rest-of-queens (list new-row)))

(define (safe? q1y positions)
  (define (threatens q2y)
    (let ((q1x (list-ref positions (dec q1y)))
          (q2x (list-ref positions (dec q2y))))
      (and (not (= q1y q2y))
           (or (= q1x q2x)
               (= (abs (- q1x q2x)) (abs (- q1y q2y)))))))
  (null? (filter threatens (enumerate-interval 1 q1y))))

My mai difficulty was from how I made the column position implicit, so it was difficult to think about until I decided to represent it properly by calling list-ref.

First time I’ve solved the 8 queens problem so this was satisfying.

2.43

queen-cols recursively calls itself 8 times, instead of 1 like in the first implementation. queen cols is called 8 times in the better implementation. For the slow implementation, queen-cols is called 8^8 times, so it takes about 8^7 times as long, which is about 2 million times as long as T.

2.44

Because I can’t easily find a picture language implementation for guile and can’t be bothered to learn a different scheme implementation, I’m going to skip this. Might be good for a future project.

Pretty much finished 2.2. It was too bad I couldn’t jump into the picture language stuff as it looks fun, but I think I am reasonably clear with the concepts that have been introduced. Not much else to say except that working through the exercises has been fun.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s