read

;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 (flatmap proc seq)
(accumulate append nil (map proc seq)))

(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))

(define nil (list))

(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(
else (filter predicate (cdr sequence)))))

(define (enumerate-interval low high)
(
if (> low high)
nil
(cons low (enumerate
-interval (+ low 1) high))))

;Solution
(define empty-board (list))
(define (adjoin
-position new-row k rest-of-queens) (append rest-of-queens (list new-row)))
(define (safe
? k position)
(define (iter col i)
(cond ((
= i k) #t)
((and (SafeCol
? position (- k i) col) (SafeCol? position (- k i) (+ col i)) (SafeCol? position (- k i) (- col i)))
(iter col (
+ i 1)))
(
else #f)))
(iter (colValue k position)
1))
(define (colValue k position)
(
if (= k 1) (car position)
(colValue (
- k 1) (cdr position))))
(define (SafeCol
? position checkcol col)
(not (
= col (colValue checkcol position))))

Blog Logo

Ki Sung Bae


Published

Image

Gsong's Blog

Developer + Entrepreneur = Entreveloper

Back to Overview