1 (define (test-case actual expected)
2   (newline)
3   (display "Actual:   ")
4   (display actual)
5   (newline)
6   (display "Expected: ")
7   (display expected)
8   (newline))
9 
10 (define (flatmap proc seq)
11   (fold-right append '() (map proc seq)))
12 (define (enumerate-interval low high)
13   (if (> low high)
14       '()
15       (cons low (enumerate-interval (1+ low) high))))
16 
17 (define (queens board-size)
18   (define (queen-cols k)  
19     (if (= k 0)
20         (list empty-board)
21         (filter
22          (lambda (positions) (safe? k positions))
23          (flatmap
24           (lambda (rest-of-queens)
25             (map (lambda (new-row)
26                    (adjoin-position new-row k rest-of-queens))
27                  (enumerate-interval 1 board-size)))
28           (queen-cols (- k 1))))))
29   (queen-cols board-size))
30 
31 ;; For example, '(((2 1) (4 2) (1 3) (3 4))) represents col#1 row#2, col#2 row#4, col#3 row#1, col#4 row#3.
32 (define empty-board '())
33 
34 ;; (adjoin-position 1 3 '((2 1) (4 2))) = '((2 1) (4 2) (1 3))
35 (define (adjoin-position row col positions)
36   (append positions (list (list row col))))
37 
38 
39 ;; not finished
40 (define (safe? col positions)
41   (define (exclude-last list)
42     (cond ((null? list) (error "empty list"))
43 	  ((null? (cdr list)) '())
44 	  (else (cons (car list) (exclude-last (cdr list))))))
45   (let ((row (list-ref positions (- col 1)))
46 	(all-but-last (exclude-last positions)))
47     (let ((same-row?
48 	   (fold-left (lambda (result next-row)
49 			(or result
50 			    (= next-row row)))
51 		      #f
52 		      all-but-last))
53 	  (same-positive-diagonal?
54 	   (fold-left (lambda (result row-col-sum)
55 			(or result
56 			    (= (+ row col) row-col-sum)))
57 		      #f
58 		      (map + all-but-last (enumerate-interval 1 (- col 1)))))
59 	  (same-negative-diagonal?
60 	   (fold-left (lambda (result row-col-dif)
61 			(or result
62 			    (= (- row col) row-col-dif)))
63 		      #f
64 		      (map - all-but-last (enumerate-interval 1 (- col 1))))))
65       (not (or same-row? same-positive-diagonal? same-negative-diagonal?)))))
66 
67 
68 ;; (test-case (safe? 1 '(1)) #t)
69 ;; (test-case (safe? 4 '(2 4 1 1)) #f)
70 ;; (test-case (safe? 4 '(2 4 1 2)) #f)
71 ;; (test-case (safe? 4 '(2 4 1 3)) #t)
72 ;; (test-case (safe? 4 '(2 4 1 4)) #f)
73 ;; (test-case (safe? 7 '(2 4 6 8 3 1 1)) #f)
74 ;; (test-case (safe? 7 '(2 4 6 8 3 1 2)) #f)
75 ;; (test-case (safe? 7 '(2 4 6 8 3 1 3)) #f)
76 ;; (test-case (safe? 7 '(2 4 6 8 3 1 4)) #f)
77 ;; (test-case (safe? 7 '(2 4 6 8 3 1 5)) #f)
78 ;; (test-case (safe? 7 '(2 4 6 8 3 1 6)) #f)
79 ;; (test-case (safe? 7 '(2 4 6 8 3 1 7)) #t)
80 ;; (test-case (safe? 7 '(2 4 6 8 3 1 8)) #f)
81 
82 
83 (queens 8)