SICP 2.2 exercises cont. 2Posted: January 27, 2013
(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.
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.
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.