sicp-ex-2.42


atomik

Like the anonymous fellow below, I represented each row of the chessboard as a single number from 1 to 8. So a "board" would just be a list of 8 numbers.

This means adjoin-position can just `cons` a number onto a list and empty-board is just the empty list

 (define (adjoin-position new-row rest-of-queens) 
     (cons new-row rest-of-queens)) 
 (define empty-board '()) 

Instead of deciding if a new row is "safe" before pushing it onto the board (as I think the authors of the SICP intended) I'm just going to push a row onto the board and then pass the whole board into `safe?`. `safe?` will then check the `car` of the board against the other rows in the board. This means our `safe?` procedure only needs to take one argument:

 (define (safe? board) 
     ; `queen` is the position of the last queen to be pushed onto the board 
     ; Conveniently, it does not need to change during this procedure 
     (let ((queen (car board))) 
         ; As we `cdr` down our board, we need to check "down" and "diagonally" 
         ; Since "down" is always the same, we can just use `queen` 
         ; The right diagonal is just `(- queen 1)` and the left diagonal is 
         ; (+ queen 1). When we call `iter` again the right and left diagonals 
         ; will be incremented and decremented. 
         ; If we make it through the whole list, that means that neither our 
         ; queen nor its diagonals matched a position in the board, so we return 
         ; true. 
         (define (iter rest-of-board right-diagonal left-diagonal) 
             (cond 
                 ((null? rest-of-board) #t) 
                 ((= queen (car rest-of-board)) #f) 
                 ((= right-diagonal (car rest-of-board)) #f) 
                 ((= left-diagonal (car rest-of-board)) #f) 
                 (else 
                     (iter 
                         (cdr rest-of-board) 
                         (+ right-diagonal -1) 
                         (+ left-diagonal 1))))) 
         ; I'm adding -1 because I don't like non-commutative operations 
         (iter (cdr board) (+ queen -1) (+ queen 1)))) 

I didn't use k for functions `adjoin-position` or `safe?` and to be honest, I have no idea how I was supposed to use k in `adjoin-position`. This problem was like one of those disturbing Ikea furniture sets that have parts left over when you finish building it that just make you wonder "what was I supposed to do with that?" `k` is really handy for tracking the size of the board, though.

 (define (queens board-size) 
     (define (queen-cols k) 
         (if (= k 0) 
             ; All of this stuff is exactly what's in the book, sans `k` 
             (list empty-board) 
             (filter 
                 (lambda (positions) (safe? positions)) 
                 (flatmap 
                     (lambda (rest-of-queens) 
                         (map (lambda (new-row) 
                                 (adjoin-position new-row rest-of-queens)) 
                             (enumerate-interval 1 board-size))) 
                     (queen-cols (+ k -1)))))) 
     (queen-cols board-size)) 

I got up to (queens 13). There are 73,712 solutions out of ~10^14 possible boards. I tried to do (queens 14) run but I got bored after a few minutes and stopped the program.


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)