1 665c255d 2023-08-04 jrmu (define (test-case actual expected)
3 665c255d 2023-08-04 jrmu (display "Actual: ")
4 665c255d 2023-08-04 jrmu (display actual)
6 665c255d 2023-08-04 jrmu (display "Expected: ")
7 665c255d 2023-08-04 jrmu (display expected)
10 665c255d 2023-08-04 jrmu (define (flatmap proc seq)
11 665c255d 2023-08-04 jrmu (fold-right append '() (map proc seq)))
12 665c255d 2023-08-04 jrmu (define (enumerate-interval low high)
13 665c255d 2023-08-04 jrmu (if (> low high)
15 665c255d 2023-08-04 jrmu (cons low (enumerate-interval (1+ low) high))))
18 665c255d 2023-08-04 jrmu (define (queens board-size)
19 665c255d 2023-08-04 jrmu (define (queen-cols k)
21 665c255d 2023-08-04 jrmu (list empty-board)
23 665c255d 2023-08-04 jrmu (lambda (positions) (safe? k positions))
25 665c255d 2023-08-04 jrmu (lambda (rest-of-queens)
26 665c255d 2023-08-04 jrmu (map (lambda (new-row)
27 665c255d 2023-08-04 jrmu (adjoin-position new-row k rest-of-queens))
28 665c255d 2023-08-04 jrmu (enumerate-interval 1 board-size)))
29 665c255d 2023-08-04 jrmu (queen-cols (- k 1))))))
30 665c255d 2023-08-04 jrmu (queen-cols board-size))
32 665c255d 2023-08-04 jrmu ;; 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 665c255d 2023-08-04 jrmu (define empty-board '())
35 665c255d 2023-08-04 jrmu ;; take positions and append new-queen-row in the (new-queen-col - 1)st position in the list
36 665c255d 2023-08-04 jrmu (define (adjoin-position new-queen-row new-queen-col positions)
37 665c255d 2023-08-04 jrmu (append positions
38 665c255d 2023-08-04 jrmu (list new-queen-row)))
39 665c255d 2023-08-04 jrmu (define (safe? col positions)
40 665c255d 2023-08-04 jrmu (define (exclude-last list)
41 665c255d 2023-08-04 jrmu (cond ((null? list) (error "empty list"))
42 665c255d 2023-08-04 jrmu ((null? (cdr list)) '())
43 665c255d 2023-08-04 jrmu (else (cons (car list) (exclude-last (cdr list))))))
44 665c255d 2023-08-04 jrmu (let ((row (list-ref positions (- col 1)))
45 665c255d 2023-08-04 jrmu (all-but-last (exclude-last positions)))
46 665c255d 2023-08-04 jrmu (let ((same-row?
47 665c255d 2023-08-04 jrmu (fold-left (lambda (result next-row)
49 665c255d 2023-08-04 jrmu (= next-row row)))
51 665c255d 2023-08-04 jrmu all-but-last))
52 665c255d 2023-08-04 jrmu (same-positive-diagonal?
53 665c255d 2023-08-04 jrmu (fold-left (lambda (result row-col-sum)
55 665c255d 2023-08-04 jrmu (= (+ row col) row-col-sum)))
57 665c255d 2023-08-04 jrmu (map + all-but-last (enumerate-interval 1 (- col 1)))))
58 665c255d 2023-08-04 jrmu (same-negative-diagonal?
59 665c255d 2023-08-04 jrmu (fold-left (lambda (result row-col-dif)
61 665c255d 2023-08-04 jrmu (= (- row col) row-col-dif)))
63 665c255d 2023-08-04 jrmu (map - all-but-last (enumerate-interval 1 (- col 1))))))
64 665c255d 2023-08-04 jrmu (not (or same-row? same-positive-diagonal? same-negative-diagonal?)))))
67 665c255d 2023-08-04 jrmu ;; (test-case (safe? 1 '(1)) #t)
68 665c255d 2023-08-04 jrmu ;; (test-case (safe? 4 '(2 4 1 1)) #f)
69 665c255d 2023-08-04 jrmu ;; (test-case (safe? 4 '(2 4 1 2)) #f)
70 665c255d 2023-08-04 jrmu ;; (test-case (safe? 4 '(2 4 1 3)) #t)
71 665c255d 2023-08-04 jrmu ;; (test-case (safe? 4 '(2 4 1 4)) #f)
72 665c255d 2023-08-04 jrmu ;; (test-case (safe? 7 '(2 4 6 8 3 1 1)) #f)
73 665c255d 2023-08-04 jrmu ;; (test-case (safe? 7 '(2 4 6 8 3 1 2)) #f)
74 665c255d 2023-08-04 jrmu ;; (test-case (safe? 7 '(2 4 6 8 3 1 3)) #f)
75 665c255d 2023-08-04 jrmu ;; (test-case (safe? 7 '(2 4 6 8 3 1 4)) #f)
76 665c255d 2023-08-04 jrmu ;; (test-case (safe? 7 '(2 4 6 8 3 1 5)) #f)
77 665c255d 2023-08-04 jrmu ;; (test-case (safe? 7 '(2 4 6 8 3 1 6)) #f)
78 665c255d 2023-08-04 jrmu ;; (test-case (safe? 7 '(2 4 6 8 3 1 7)) #t)
79 665c255d 2023-08-04 jrmu ;; (test-case (safe? 7 '(2 4 6 8 3 1 8)) #f)
