196 lines
9.5 KiB
Racket
196 lines
9.5 KiB
Racket
#lang sicp
|
|
|
|
(#%require racket/trace)
|
|
(#%require (only racket/base time))
|
|
|
|
;; From the book
|
|
|
|
(define (filter predicate sequence)
|
|
(cond ((null? sequence) nil)
|
|
((predicate (car sequence))
|
|
(cons (car sequence)
|
|
(filter predicate (cdr sequence))))
|
|
(else (filter predicate (cdr sequence)))))
|
|
|
|
(define (accumulate op initial sequence)
|
|
(if (null? sequence)
|
|
initial
|
|
(op (car sequence)
|
|
(accumulate op initial (cdr sequence)))))
|
|
|
|
(define (flatmap proc seq)
|
|
(accumulate append nil (map proc seq)))
|
|
|
|
(define (enumerate-interval low high)
|
|
(if (> low high)
|
|
nil
|
|
(cons low (enumerate-interval (+ low 1) high))))
|
|
|
|
;; EXERCISE 2.42
|
|
|
|
|
|
(define (queens board-size)
|
|
(define (queen-cols k)
|
|
(if (= k 0)
|
|
(list empty-board)
|
|
(filter
|
|
(lambda (positions) (safe? k positions))
|
|
(flatmap
|
|
(lambda (rest-of-queens)
|
|
(map (lambda (new-row)
|
|
(adjoin-position new-row k rest-of-queens))
|
|
(enumerate-interval 1 board-size)))
|
|
(queen-cols (- k 1))))))
|
|
(queen-cols board-size))
|
|
|
|
|
|
(define empty-board '())
|
|
|
|
(define (position row col) (cons row col))
|
|
(define (row position) (car position))
|
|
(define (col position) (cdr position))
|
|
|
|
(define (adjoin-position row col rest-of-queens)
|
|
(append rest-of-queens (list (position row col))))
|
|
|
|
(define (safe? k positions)
|
|
;; Compute the y-intercepts of the horizontal line the line of
|
|
;; gradient +1 and the line of gradient -1 through the given
|
|
;; position. Any two positions that share one of these intercepts
|
|
;; lie on the same diagonal and are thus not safe wrt each other.
|
|
(define (positive-intercept position)
|
|
(- (row position) (col position)))
|
|
(define (negative-intercept position)
|
|
(+ (row position) (col position)))
|
|
(let ((kth-position (list-ref positions (- k 1)))
|
|
(pre-kth-positions (cdr (reverse positions))))
|
|
;; If the row, positive or negative intercept of the k-th position
|
|
;; is equal to any of the first k-1 positions, then the k-th
|
|
;; position is not safe.
|
|
(and (not (memv (row kth-position)
|
|
(map row pre-kth-positions)))
|
|
(not (memv (positive-intercept kth-position)
|
|
(map positive-intercept pre-kth-positions)))
|
|
(not (memv (negative-intercept kth-position)
|
|
(map negative-intercept pre-kth-positions))))))
|
|
|
|
|
|
;; ;; Output
|
|
|
|
;; (((1 . 1) (5 . 2) (8 . 3) (6 . 4) (3 . 5) (7 . 6) (2 . 7) (4 . 8))
|
|
;; ((1 . 1) (6 . 2) (8 . 3) (3 . 4) (7 . 5) (4 . 6) (2 . 7) (5 . 8))
|
|
;; ((1 . 1) (7 . 2) (4 . 3) (6 . 4) (8 . 5) (2 . 6) (5 . 7) (3 . 8))
|
|
;; ((1 . 1) (7 . 2) (5 . 3) (8 . 4) (2 . 5) (4 . 6) (6 . 7) (3 . 8))
|
|
;; ((2 . 1) (4 . 2) (6 . 3) (8 . 4) (3 . 5) (1 . 6) (7 . 7) (5 . 8))
|
|
;; ((2 . 1) (5 . 2) (7 . 3) (1 . 4) (3 . 5) (8 . 6) (6 . 7) (4 . 8))
|
|
;; ((2 . 1) (5 . 2) (7 . 3) (4 . 4) (1 . 5) (8 . 6) (6 . 7) (3 . 8))
|
|
;; ((2 . 1) (6 . 2) (1 . 3) (7 . 4) (4 . 5) (8 . 6) (3 . 7) (5 . 8))
|
|
;; ((2 . 1) (6 . 2) (8 . 3) (3 . 4) (1 . 5) (4 . 6) (7 . 7) (5 . 8))
|
|
;; ((2 . 1) (7 . 2) (3 . 3) (6 . 4) (8 . 5) (5 . 6) (1 . 7) (4 . 8))
|
|
;; ((2 . 1) (7 . 2) (5 . 3) (8 . 4) (1 . 5) (4 . 6) (6 . 7) (3 . 8))
|
|
;; ((2 . 1) (8 . 2) (6 . 3) (1 . 4) (3 . 5) (5 . 6) (7 . 7) (4 . 8))
|
|
;; ((3 . 1) (1 . 2) (7 . 3) (5 . 4) (8 . 5) (2 . 6) (4 . 7) (6 . 8))
|
|
;; ((3 . 1) (5 . 2) (2 . 3) (8 . 4) (1 . 5) (7 . 6) (4 . 7) (6 . 8))
|
|
;; ((3 . 1) (5 . 2) (2 . 3) (8 . 4) (6 . 5) (4 . 6) (7 . 7) (1 . 8))
|
|
;; ((3 . 1) (5 . 2) (7 . 3) (1 . 4) (4 . 5) (2 . 6) (8 . 7) (6 . 8))
|
|
;; ((3 . 1) (5 . 2) (8 . 3) (4 . 4) (1 . 5) (7 . 6) (2 . 7) (6 . 8))
|
|
;; ((3 . 1) (6 . 2) (2 . 3) (5 . 4) (8 . 5) (1 . 6) (7 . 7) (4 . 8))
|
|
;; ((3 . 1) (6 . 2) (2 . 3) (7 . 4) (1 . 5) (4 . 6) (8 . 7) (5 . 8))
|
|
;; ((3 . 1) (6 . 2) (2 . 3) (7 . 4) (5 . 5) (1 . 6) (8 . 7) (4 . 8))
|
|
;; ((3 . 1) (6 . 2) (4 . 3) (1 . 4) (8 . 5) (5 . 6) (7 . 7) (2 . 8))
|
|
;; ((3 . 1) (6 . 2) (4 . 3) (2 . 4) (8 . 5) (5 . 6) (7 . 7) (1 . 8))
|
|
;; ((3 . 1) (6 . 2) (8 . 3) (1 . 4) (4 . 5) (7 . 6) (5 . 7) (2 . 8))
|
|
;; ((3 . 1) (6 . 2) (8 . 3) (1 . 4) (5 . 5) (7 . 6) (2 . 7) (4 . 8))
|
|
;; ((3 . 1) (6 . 2) (8 . 3) (2 . 4) (4 . 5) (1 . 6) (7 . 7) (5 . 8))
|
|
;; ((3 . 1) (7 . 2) (2 . 3) (8 . 4) (5 . 5) (1 . 6) (4 . 7) (6 . 8))
|
|
;; ((3 . 1) (7 . 2) (2 . 3) (8 . 4) (6 . 5) (4 . 6) (1 . 7) (5 . 8))
|
|
;; ((3 . 1) (8 . 2) (4 . 3) (7 . 4) (1 . 5) (6 . 6) (2 . 7) (5 . 8))
|
|
;; ((4 . 1) (1 . 2) (5 . 3) (8 . 4) (2 . 5) (7 . 6) (3 . 7) (6 . 8))
|
|
;; ((4 . 1) (1 . 2) (5 . 3) (8 . 4) (6 . 5) (3 . 6) (7 . 7) (2 . 8))
|
|
;; ((4 . 1) (2 . 2) (5 . 3) (8 . 4) (6 . 5) (1 . 6) (3 . 7) (7 . 8))
|
|
;; ((4 . 1) (2 . 2) (7 . 3) (3 . 4) (6 . 5) (8 . 6) (1 . 7) (5 . 8))
|
|
;; ((4 . 1) (2 . 2) (7 . 3) (3 . 4) (6 . 5) (8 . 6) (5 . 7) (1 . 8))
|
|
;; ((4 . 1) (2 . 2) (7 . 3) (5 . 4) (1 . 5) (8 . 6) (6 . 7) (3 . 8))
|
|
;; ((4 . 1) (2 . 2) (8 . 3) (5 . 4) (7 . 5) (1 . 6) (3 . 7) (6 . 8))
|
|
;; ((4 . 1) (2 . 2) (8 . 3) (6 . 4) (1 . 5) (3 . 6) (5 . 7) (7 . 8))
|
|
;; ((4 . 1) (6 . 2) (1 . 3) (5 . 4) (2 . 5) (8 . 6) (3 . 7) (7 . 8))
|
|
;; ((4 . 1) (6 . 2) (8 . 3) (2 . 4) (7 . 5) (1 . 6) (3 . 7) (5 . 8))
|
|
;; ((4 . 1) (6 . 2) (8 . 3) (3 . 4) (1 . 5) (7 . 6) (5 . 7) (2 . 8))
|
|
;; ((4 . 1) (7 . 2) (1 . 3) (8 . 4) (5 . 5) (2 . 6) (6 . 7) (3 . 8))
|
|
;; ((4 . 1) (7 . 2) (3 . 3) (8 . 4) (2 . 5) (5 . 6) (1 . 7) (6 . 8))
|
|
;; ((4 . 1) (7 . 2) (5 . 3) (2 . 4) (6 . 5) (1 . 6) (3 . 7) (8 . 8))
|
|
;; ((4 . 1) (7 . 2) (5 . 3) (3 . 4) (1 . 5) (6 . 6) (8 . 7) (2 . 8))
|
|
;; ((4 . 1) (8 . 2) (1 . 3) (3 . 4) (6 . 5) (2 . 6) (7 . 7) (5 . 8))
|
|
;; ((4 . 1) (8 . 2) (1 . 3) (5 . 4) (7 . 5) (2 . 6) (6 . 7) (3 . 8))
|
|
;; ((4 . 1) (8 . 2) (5 . 3) (3 . 4) (1 . 5) (7 . 6) (2 . 7) (6 . 8))
|
|
;; ((5 . 1) (1 . 2) (4 . 3) (6 . 4) (8 . 5) (2 . 6) (7 . 7) (3 . 8))
|
|
;; ((5 . 1) (1 . 2) (8 . 3) (4 . 4) (2 . 5) (7 . 6) (3 . 7) (6 . 8))
|
|
;; ((5 . 1) (1 . 2) (8 . 3) (6 . 4) (3 . 5) (7 . 6) (2 . 7) (4 . 8))
|
|
;; ((5 . 1) (2 . 2) (4 . 3) (6 . 4) (8 . 5) (3 . 6) (1 . 7) (7 . 8))
|
|
;; ((5 . 1) (2 . 2) (4 . 3) (7 . 4) (3 . 5) (8 . 6) (6 . 7) (1 . 8))
|
|
;; ((5 . 1) (2 . 2) (6 . 3) (1 . 4) (7 . 5) (4 . 6) (8 . 7) (3 . 8))
|
|
;; ((5 . 1) (2 . 2) (8 . 3) (1 . 4) (4 . 5) (7 . 6) (3 . 7) (6 . 8))
|
|
;; ((5 . 1) (3 . 2) (1 . 3) (6 . 4) (8 . 5) (2 . 6) (4 . 7) (7 . 8))
|
|
;; ((5 . 1) (3 . 2) (1 . 3) (7 . 4) (2 . 5) (8 . 6) (6 . 7) (4 . 8))
|
|
;; ((5 . 1) (3 . 2) (8 . 3) (4 . 4) (7 . 5) (1 . 6) (6 . 7) (2 . 8))
|
|
;; ((5 . 1) (7 . 2) (1 . 3) (3 . 4) (8 . 5) (6 . 6) (4 . 7) (2 . 8))
|
|
;; ((5 . 1) (7 . 2) (1 . 3) (4 . 4) (2 . 5) (8 . 6) (6 . 7) (3 . 8))
|
|
;; ((5 . 1) (7 . 2) (2 . 3) (4 . 4) (8 . 5) (1 . 6) (3 . 7) (6 . 8))
|
|
;; ((5 . 1) (7 . 2) (2 . 3) (6 . 4) (3 . 5) (1 . 6) (4 . 7) (8 . 8))
|
|
;; ((5 . 1) (7 . 2) (2 . 3) (6 . 4) (3 . 5) (1 . 6) (8 . 7) (4 . 8))
|
|
;; ((5 . 1) (7 . 2) (4 . 3) (1 . 4) (3 . 5) (8 . 6) (6 . 7) (2 . 8))
|
|
;; ((5 . 1) (8 . 2) (4 . 3) (1 . 4) (3 . 5) (6 . 6) (2 . 7) (7 . 8))
|
|
;; ((5 . 1) (8 . 2) (4 . 3) (1 . 4) (7 . 5) (2 . 6) (6 . 7) (3 . 8))
|
|
;; ((6 . 1) (1 . 2) (5 . 3) (2 . 4) (8 . 5) (3 . 6) (7 . 7) (4 . 8))
|
|
;; ((6 . 1) (2 . 2) (7 . 3) (1 . 4) (3 . 5) (5 . 6) (8 . 7) (4 . 8))
|
|
;; ((6 . 1) (2 . 2) (7 . 3) (1 . 4) (4 . 5) (8 . 6) (5 . 7) (3 . 8))
|
|
;; ((6 . 1) (3 . 2) (1 . 3) (7 . 4) (5 . 5) (8 . 6) (2 . 7) (4 . 8))
|
|
;; ((6 . 1) (3 . 2) (1 . 3) (8 . 4) (4 . 5) (2 . 6) (7 . 7) (5 . 8))
|
|
;; ((6 . 1) (3 . 2) (1 . 3) (8 . 4) (5 . 5) (2 . 6) (4 . 7) (7 . 8))
|
|
;; ((6 . 1) (3 . 2) (5 . 3) (7 . 4) (1 . 5) (4 . 6) (2 . 7) (8 . 8))
|
|
;; ((6 . 1) (3 . 2) (5 . 3) (8 . 4) (1 . 5) (4 . 6) (2 . 7) (7 . 8))
|
|
;; ((6 . 1) (3 . 2) (7 . 3) (2 . 4) (4 . 5) (8 . 6) (1 . 7) (5 . 8))
|
|
;; ((6 . 1) (3 . 2) (7 . 3) (2 . 4) (8 . 5) (5 . 6) (1 . 7) (4 . 8))
|
|
;; ((6 . 1) (3 . 2) (7 . 3) (4 . 4) (1 . 5) (8 . 6) (2 . 7) (5 . 8))
|
|
;; ((6 . 1) (4 . 2) (1 . 3) (5 . 4) (8 . 5) (2 . 6) (7 . 7) (3 . 8))
|
|
;; ((6 . 1) (4 . 2) (2 . 3) (8 . 4) (5 . 5) (7 . 6) (1 . 7) (3 . 8))
|
|
;; ((6 . 1) (4 . 2) (7 . 3) (1 . 4) (3 . 5) (5 . 6) (2 . 7) (8 . 8))
|
|
;; ((6 . 1) (4 . 2) (7 . 3) (1 . 4) (8 . 5) (2 . 6) (5 . 7) (3 . 8))
|
|
;; ((6 . 1) (8 . 2) (2 . 3) (4 . 4) (1 . 5) (7 . 6) (5 . 7) (3 . 8))
|
|
;; ((7 . 1) (1 . 2) (3 . 3) (8 . 4) (6 . 5) (4 . 6) (2 . 7) (5 . 8))
|
|
;; ((7 . 1) (2 . 2) (4 . 3) (1 . 4) (8 . 5) (5 . 6) (3 . 7) (6 . 8))
|
|
;; ((7 . 1) (2 . 2) (6 . 3) (3 . 4) (1 . 5) (4 . 6) (8 . 7) (5 . 8))
|
|
;; ((7 . 1) (3 . 2) (1 . 3) (6 . 4) (8 . 5) (5 . 6) (2 . 7) (4 . 8))
|
|
;; ((7 . 1) (3 . 2) (8 . 3) (2 . 4) (5 . 5) (1 . 6) (6 . 7) (4 . 8))
|
|
;; ((7 . 1) (4 . 2) (2 . 3) (5 . 4) (8 . 5) (1 . 6) (3 . 7) (6 . 8))
|
|
;; ((7 . 1) (4 . 2) (2 . 3) (8 . 4) (6 . 5) (1 . 6) (3 . 7) (5 . 8))
|
|
;; ((7 . 1) (5 . 2) (3 . 3) (1 . 4) (6 . 5) (8 . 6) (2 . 7) (4 . 8))
|
|
;; ((8 . 1) (2 . 2) (4 . 3) (1 . 4) (7 . 5) (5 . 6) (3 . 7) (6 . 8))
|
|
;; ((8 . 1) (2 . 2) (5 . 3) (3 . 4) (1 . 5) (7 . 6) (4 . 7) (6 . 8))
|
|
;; ((8 . 1) (3 . 2) (1 . 3) (6 . 4) (2 . 5) (5 . 6) (7 . 7) (4 . 8))
|
|
;; ((8 . 1) (4 . 2) (1 . 3) (3 . 4) (6 . 5) (2 . 6) (7 . 7) (5 . 8)))
|
|
|
|
;; Exercise 2.43
|
|
|
|
;; This is slower than the first version from the book because
|
|
;; (queen-cols (- k 1)) is inside the inner lambda and so is
|
|
;; re-evaluated recursively for each new row (ie board-size times).
|
|
;; The faster version evaluates (queen-cols (- k 1)) only once in the
|
|
;; outer flatmap.
|
|
|
|
;; So if the faster version takes time T, this version will take
|
|
;; approximately time
|
|
(define (queens-slow board-size)
|
|
(define (queen-cols k)
|
|
(if (= k 0)
|
|
(list empty-board)
|
|
(filter
|
|
(lambda (positions) (safe? k positions))
|
|
(flatmap
|
|
(lambda (new-row)
|
|
(map (lambda (rest-of-queens)
|
|
(adjoin-position new-row k rest-of-queens))
|
|
(queen-cols (- k 1))))
|
|
(enumerate-interval 1 board-size)))))
|
|
(queen-cols board-size))
|