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 
18 (define (queens board-size)
19   (define (queen-cols k)  
20     (if (= k 0)
21         (list empty-board)
22         (filter
23          (lambda (positions) (safe? k positions))
24          (flatmap
25           (lambda (rest-of-queens)
26             (map (lambda (new-row)
27                    (adjoin-position new-row k rest-of-queens))
28                  (enumerate-interval 1 board-size)))
29           (queen-cols (- k 1))))))
30   (queen-cols board-size))
31 
32 ;; For example, '((2 4 1 3)) might represent a solution to the 4-queens problem. This represents having queens in col#1 row#2, col#2 row#4, col#3 row#1, col#4 row#3.
33 (define empty-board '())
34 
35 ;; take positions and append new-queen-row in the (new-queen-col - 1)st position in the list
36 (define (adjoin-position new-queen-row new-queen-col positions)
37   (append positions
38 	  (list new-queen-row)))
39 (define (safe? col positions)
40   (define (exclude-last list)
41     (cond ((null? list) (error "empty list"))
42 	  ((null? (cdr list)) '())
43 	  (else (cons (car list) (exclude-last (cdr list))))))
44   (let ((row (list-ref positions (- col 1)))
45 	(all-but-last (exclude-last positions)))
46     (let ((same-row?
47 	   (fold-left (lambda (result next-row)
48 			(or result
49 			    (= next-row row)))
50 		      #f
51 		      all-but-last))
52 	  (same-positive-diagonal?
53 	   (fold-left (lambda (result row-col-sum)
54 			(or result
55 			    (= (+ row col) row-col-sum)))
56 		      #f
57 		      (map + all-but-last (enumerate-interval 1 (- col 1)))))
58 	  (same-negative-diagonal?
59 	   (fold-left (lambda (result row-col-dif)
60 			(or result
61 			    (= (- row col) row-col-dif)))
62 		      #f
63 		      (map - all-but-last (enumerate-interval 1 (- col 1))))))
64       (not (or same-row? same-positive-diagonal? same-negative-diagonal?)))))
65 
66 
67 ;; (test-case (safe? 1 '(1)) #t)
68 ;; (test-case (safe? 4 '(2 4 1 1)) #f)
69 ;; (test-case (safe? 4 '(2 4 1 2)) #f)
70 ;; (test-case (safe? 4 '(2 4 1 3)) #t)
71 ;; (test-case (safe? 4 '(2 4 1 4)) #f)
72 ;; (test-case (safe? 7 '(2 4 6 8 3 1 1)) #f)
73 ;; (test-case (safe? 7 '(2 4 6 8 3 1 2)) #f)
74 ;; (test-case (safe? 7 '(2 4 6 8 3 1 3)) #f)
75 ;; (test-case (safe? 7 '(2 4 6 8 3 1 4)) #f)
76 ;; (test-case (safe? 7 '(2 4 6 8 3 1 5)) #f)
77 ;; (test-case (safe? 7 '(2 4 6 8 3 1 6)) #f)
78 ;; (test-case (safe? 7 '(2 4 6 8 3 1 7)) #t)
79 ;; (test-case (safe? 7 '(2 4 6 8 3 1 8)) #f)
80 
81 
82 (queens 8)