sicp-ex-2.42


3pmtea

I'm using a representation like below:

(((row1 col1) (row2 col2) ...) ......)

It's a list of all solutions, where a solution is a list of coordinates, where a coordinate is (list row col).

So empty-board and adjoin-position can be defined as follows:

   (define empty-board '()) 
   (define (adjoin-position row col rest) 
     (cons (list row col) rest)) 

The safe? procedure is a little complex:

   (define (safe? k positions) 
     (let ((trial (car positions)) 
           (trial-row (caar positions)) 
           (trial-col (cadar positions)) 
           (rest (cdr positions))) 
       (accumulate (lambda (pos result) 
                     (let ((row (car pos)) 
                           (col (cadr pos))) 
                       (and (not (= (- trial-row trial-col) 
                                    (- row col))) 
                            (not (= (+ trial-row trial-col) 
                                    (+ row col))) 
                            (not (= trial-row row)) 
                            result))) 
                   true 
                   rest))) 

I'm not using any procedures that are beyond the textbook, and the parameter k is not necessary here.



This method generates all 92 solutions. It will work up to (queens 9) but runs out of memory for (queens 10).

A position is represented as an ordered list 8 numbers eg (1 3 6 8 2 4 9 7 5), which denotes queen positions row 1 col 1, row 2 col 3,...,row 8 col 5

Check-row tests a row against the succeeding rows to make sure no two queens share a diagonal.

 (define (queens n)
     (define (check-row p k)
        (define (iter k count)
           (cond ((= count (+ n 1)) true)
                 (else (if (or (= (abs (-  count
                                           k))
                                  (abs (- (list-ref p (- count 1))
                                          (list-ref p (- k 1)))))
                               (= (+ k
                                     (list-ref p (- k 1)))
                                  (+ count
                                     (list-ref p (- count 1)))))
                           false
                           (iter k (+ count 1))))))
        (iter k (+ k 1)))
     (define (check p)
         (define (iter p count)
            (cond ((= count n) true)
                  (else (if (not (check-row p count))
                            false
                            (iter p (+ count 1))))))
         (iter p 1))
     (filter (lambda (x) (check x))
             (permutations (enumerate-interval 1 n))))
 (queens 8)