Exercise 4.44.  Exercise 2.42 described the ``eight-queens puzzle'' of 
placing queens on a chessboard so that no two attack each other. Write a 
nondeterministic program to solve this puzzle.

————————————————————————————————————————————————————————————————————————

(define (eight-queens)
  (define (add-queens position n)
    (if (= n 0)
        position
        (let ((new-queen (list n (amb 1 2 3 4 5 6 7 8))))
          (require (all (map (lambda (queen) (not-checking new-queen queen))
                             position)))
          (add-queens (cons new-queen position) (- n 1)))))
  (add-queens '() 8))

(define (all items)
  (cond ((null? items) #t)
        ((false? (car items)) #f)
        (else (all (cdr items)))))

(define (not-checking q1 q2) (not (checking q1 q2)))

(define (checking q1 q2)
  (or (= (car q1) (car q2)) // same column
      (= (cadr q1) (cadr q2)) // same row
      (= (abs (- (car q1) (car q2)))
         (abs (- (cadr q1) (cadr q2)))))) // same diagonal