►zthomae’s SICP solutions
▼2 Chapter 2
2.1 Exercise 2.1
2.2 Exercise 2.2
2.3 Exercise 2.3
2.4 Exercise 2.4
2.5 Exercise 2.5
2.6 Exercise 2.6
2.7 Exercise 2.7
2.8 Exercise 2.8
2.9 Exercise 2.9
2.10 Exercise 2.10
2.11 Exercise 2.11
2.12 Exercise 2.12
2.13 Exercise 2.13
2.14 Exercise 2.14
2.15 Exercise 2.15
2.16 Exercise 2.16
2.17 Exercise 2.17
2.18 Exercise 2.18
2.19 Exercise 2.19
2.20 Exercise 2.20
2.21 Exercise 2.21
2.22 Exercise 2.22
2.23 Exercise 2.23
2.24 Exercise 2.24
2.25 Exercise 2.25
2.26 Exercise 2.26
2.27 Exercise 2.27
2.28 Exercise 2.28
2.29 Exercise 2.29
2.30 Exercise 2.30
2.31 Exercise 2.31
2.32 Exercise 2.32
2.33 Exercise 2.33
2.34 Exercise 2.34
2.35 Exercise 2.35
2.36 Exercise 2.36
2.37 Exercise 2.37
2.38 Exercise 2.38
2.39 Exercise 2.39
2.40 Exercise 2.40
2.41 Exercise 2.41
2.42 Exercise 2.42
2.43 Exercise 2.43
2.44 Exercise 2.44
2.45 Exercise 2.45
2.46 Exercise 2.46
2.47 Exercise 2.47
2.48 Exercise 2.48
2.49 Exercise 2.49
2.50 Exercise 2.50
2.51 Exercise 2.51
2.52 Exercise 2.52
2.53 Exercise 2.53
2.54 Exercise 2.54
2.55 Exercise 2.55
2.56 Exercise 2.56
2.57 Exercise 2.57
2.58 Exercise 2.58
2.59 Exercise 2.59
2.60 Exercise 2.60
2.61 Exercise 2.61
2.62 Exercise 2.62
2.63 Exercise 2.63
2.64 Exercise 2.64
2.65 Exercise 2.65
2.66 Exercise 2.66
2.67 Exercise 2.67
2.68 Exercise 2.68
2.69 Exercise 2.69
2.70 Exercise 2.70
2.71 Exercise 2.71
2.72 Exercise 2.72
2.73 Exercise 2.73
2.74 Exercise 2.74
2.75 Exercise 2.75
2.76 Exercise 2.76
2.77 Exercise 2.77
2.78 Exercise 2.78
2.79 Exercise 2.79
2.80 Exercise 2.80
2.81 Exercise 2.81
2.82 Exercise 2.82
2.83 Exercise 2.83
2.84 Exercise 2.84
2.85 Exercise 2.85
2.86 Exercise 2.86
2.87 Exercise 2.87
2.88 Exercise 2.88
2.89 Exercise 2.89
2.90 Exercise 2.90
2.91 Exercise 2.91
2.92 Exercise 2.92
2.93 Exercise 2.93
2.94 Exercise 2.94
2.95 Exercise 2.95
2.96 Exercise 2.96
2.97 Exercise 2.97
    ← prev  up  next → 

2.42 Exercise 2.42

I consider this exercise unfinished

First, a utility procedure for finding if any element in a sequence evaluates to true:

(define (any? s)
  (cond ((null? s) #f)
        ((car s) #t)
        (else (any? (cdr s)))))

We can use this in the safe? procedure, testing if the new piece conflicts with any of the other ones. This uses a conflicts? procedure which tests if two pieces lay in the same row or on a diagonal.

(define (safe? k positions)
  (define (conflicts? positions i j)
    (let ((ri (list-ref positions i))
          (rj (list-ref positions j)))
      (or
       (= ri rj)
       (on-diagonal? i ri j rj))))
  (not
   (any?
    (map (lambda (i) (conflicts? positions i (- k 1)))
         (enumerate-interval 0 (- k 2))))))

The procedure on-diagonal? has an awkward interface and is sort of obscure. Assuming that the j is greater than i, it returns true if either the element in column j is in the space j - i rows above the element in row i (meaning the piece in column j is diagonally up and to the right from that in i), or if the reverse is true and the piece in column i is on an upper diagonal from that in column j.

(define (on-diagonal? i ri j rj)
 
  (let ((d (- j i)))
    (or
 
     (= rj (+ ri d))
 
     (= ri (+ rj d)))))

Simply representing the current queen position as a list with one element per queen, it is natural that empty-board is just an empty list and that adjoin-position just appends the new position to the end of an existing list:

(define empty-board nil)
(define (adjoin-position new-row k rest-of-queens)
  (append rest-of-queens (list new-row)))

adjoin-position takes the new column k in the given queens procedure.

    ← prev  up  next →