Chris Pollett>Old Classes>PIC 15, Fall 1999>Hw2
Read SICP 80-126 142-175. Then do the following problems from
SICP:
2.8, 2.34, 2.42.
Label your functions exactly as described in these problems. Put all your code in a single file called hw2.scm. Try to keep your representation of the board and your code as simple as possible in 2.42. My code was about 20 lines and did not need to make use of the parameter k in either the safe? or adjoin-position routines. When you have got something working try to be more clever. There is a bonus of 3 points to the person or people who write a program that returns at least one solution to the queens for the highest value of n. For the bonus you are allowed to change the queens algorithm (say using constraint satisfaction techniques); however, in what you turn in you must still have a solution to the original 2.42 problem.
Below is some code from the book for this assignment if you don't feel like typing it in:
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence))
)
)
)
(define nil ())
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence)))
)
(else (filter predicate (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))
)
)
(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)
)