; ======================================================================
;
; Structure and Interpretation of Computer Programs
; (trial answer to excercises)
;
; 计算机程序的构造和解释(习题试解)
;
; created: code17 08/19/05
; modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================
;; SICP No.2.42
(define empty-board ())
(define (adjoin-position new-row k rest-of-queens)
(cons (list k new-row) rest-of-queens))
(define (safe? k positions)
(define (check x y)
(or (= (cadr x) (cadr y))
(= (abs (- (cadr x) (cadr y)))
(abs (- (car x) (car y))))))
(let ((p (car positions))
(l (cdr positions)))
(or (= k 1) (null? (filter (lambda (x) (check x p)) l)))))
;; Test-it:
;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc.
> (queens 8)
(((8 4) (7 2) (6 7) (5 3) (4 6) (3 8) (2 5) (1 1)) ((8 5) (7 2) (6 4) (5 7) (4 3) (3 8) (2 6) (1 1)) ((8 3) (7 5) (6 2) (5 8) (4 6) (3 4) (2 7) (1 1)) ((8 3) (7 6) (6 4) (5 2) (4 8) (3 5) (2 7) (1 1)) ((8 5) (7 7) (6 1) (5 3) (4 8) (3 6) (2 4) (1 2)) ((8 4) (7 6) (6 8) (5 3) (4 1) (3 7) (2 5) (1 2)) ((8 3) (7 6) (6 8) (5 1) (4 4) (3 7) (2 5) (1 2)) ((8 5) (7 3) (6 8) (5 4) (4 7) (3 1) (2 6) (1 2)) ((8 5) (7 7) (6 4) (5 1) (4 3) (3 8) (2 6) (1 2)) ((8 4) (7 1) (6 5) (5 8) (4 6) (3 3) (2 7) (1 2)) ((8 3) (7 6) (6 4) (5 1) (4 8) (3 5) (2 7) (1 2)) ((8 4) (7 7) (6 5) (5 3) (4 1) (3 6) (2 8) (1 2)) ((8 6) (7 4) (6 2) (5 8) (4 5) (3 7) (2 1) (1 3)) ((8 6) (7 4) (6 7) (5 1) (4 8) (3 2) (2 5) (1 3)) ((8 1) (7 7) (6 4) (5 6) (4 8) (3 2) (2 5) (1 3)) ((8 6) (7 8) (6 2) (5 4) (4 1) (3 7) (2 5) (1 3)) ((8 6) (7 2) (6 7) (5 1) (4 4) (3 8) (2 5) (1 3)) ((8 4) (7 7) (6 1) (5 8) (4 5) (3 2) (2 6) (1 3)) ((8 5) (7 8) (6 4) (5 1) (4 7) (3 2) (2 6) (1 3)) ((8 4) (7 8) (6 1) (5 5) (4 7) (3 2) (2 6) (1 3)) ((8 2) (7 7) (6 5) (5 8) (4 1) (3 4) (2 6) (1 3)) ((8 1) (7 7) (6 5) (5 8) (4 2) (3 4) (2 6) (1 3)) ((8 2) (7 5) (6 7) (5 4) (4 1) (3 8) (2 6) (1 3)) ((8 4) (7 2) (6 7) (5 5) (4 1) (3 8) (2 6) (1 3)) ((8 5) (7 7) (6 1) (5 4) (4 2) (3 8) (2 6) (1 3)) ((8 6) (7 4) (6 1) (5 5) (4 8) (3 2) (2 7) (1 3)) ((8 5) (7 1) (6 4) (5 6) (4 8) (3 2) (2 7) (1 3)) ((8 5) (7 2) (6 6) (5 1) (4 7) (3 4) (2 8) (1 3)) ((8 6) (7 3) (6 7) (5 2) (4 8) (3 5) (2 1) (1 4)) ((8 2) (7 7) (6 3) (5 6) (4 8) (3 5) (2 1) (1 4)) ((8 7) (7 3) (6 1) (5 6) (4 8) (3 5) (2 2) (1 4)) ((8 5) (7 1) (6 8) (5 6) (4 3) (3 7) (2 2) (1 4)) ((8 1) (7 5) (6 8) (5 6) (4 3) (3 7) (2 2) (1 4)) ((8 3) (7 6) (6 8) (5 1) (4 5) (3 7) (2 2) (1 4)) ((8 6) (7 3) (6 1) (5 7) (4 5) (3 8) (2 2) (1 4)) ((8 7) (7 5) (6 3) (5 1) (4 6) (3 8) (2 2) (1 4)) ((8 7) (7 3) (6 8) (5 2) (4 5) (3 1) (2 6) (1 4)) ((8 5) (7 3) (6 1) (5 7) (4 2) (3 8) (2 6) (1 4)) ((8 2) (7 5) (6 7) (5 1) (4 3) (3 8) (2 6) (1 4)) ((8 3) (7 6) (6 2) (5 5) (4 8) (3 1) (2 7) (1 4)) ((8 6) (7 1) (6 5) (5 2) (4 8) (3 3) (2 7) (1 4)) ((8 8) (7 3) (6 1) (5 6) (4 2) (3 5) (2 7) (1 4)) ((8 2) (7 8) (6 6) (5 1) (4 3) (3 5) (2 7) (1 4)) ((8 5) (7 7) (6 2) (5 6) (4 3) (3 1) (2 8) (1 4)) ((8 3) (7 6) (6 2) (5 7) (4 5) (3 1) (2 8) (1 4)) ((8 6) (7 2) (6 7) (5 1) (4 3) (3 5) (2 8) (1 4)) ((8 3) (7 7) (6 2) (5 8) (4 6) (3 4) (2 1) (1 5)) ((8 6) (7 3) (6 7) (5 2) (4 4) (3 8) (2 1) (1 5)) ((8 4) (7 2) (6 7) (5 3) (4 6) (3 8) (2 1) (1 5)) ((8 7) (7 1) (6 3) (5 8) (4 6) (3 4) (2 2) (1 5)) ((8 1) (7 6) (6 8) (5 3) (4 7) (3 4) (2 2) (1 5)) ((8 3) (7 8) (6 4) (5 7) (4 1) (3 6) (2 2) (1 5)) ((8 6) (7 3) (6 7) (5 4) (4 1) (3 8) (2 2) (1 5)) ((8 7) (7 4) (6 2) (5 8) (4 6) (3 1) (2 3) (1 5)) ((8 4) (7 6) (6 8) (5 2) (4 7) (3 1) (2 3) (1 5)) ((8 2) (7 6) (6 1) (5 7) (4 4) (3 8) (2 3) (1 5)) ((8 2) (7 4) (6 6) (5 8) (4 3) (3 1) (2 7) (1 5)) ((8 3) (7 6) (6 8) (5 2) (4 4) (3 1) (2 7) (1 5)) ((8 6) (7 3) (6 1) (5 8) (4 4) (3 2) (2 7) (1 5)) ((8 8) (7 4) (6 1) (5 3) (4 6) (3 2) (2 7) (1 5)) ((8 4) (7 8) (6 1) (5 3) (4 6) (3 2) (2 7) (1 5)) ((8 2) (7 6) (6 8) (5 3) (4 1) (3 4) (2 7) (1 5)) ((8 7) (7 2) (6 6) (5 3) (4 1) (3 4) (2 8) (1 5)) ((8 3) (7 6) (6 2) (5 7) (4 1) (3 4) (2 8) (1 5)) ((8 4) (7 7) (6 3) (5 8) (4 2) (3 5) (2 1) (1 6)) ((8 4) (7 8) (6 5) (5 3) (4 1) (3 7) (2 2) (1 6)) ((8 3) (7 5) (6 8) (5 4) (4 1) (3 7) (2 2) (1 6)) ((8 4) (7 2) (6 8) (5 5) (4 7) (3 1) (2 3) (1 6)) ((8 5) (7 7) (6 2) (5 4) (4 8) (3 1) (2 3) (1 6)) ((8 7) (7 4) (6 2) (5 5) (4 8) (3 1) (2 3) (1 6)) ((8 8) (7 2) (6 4) (5 1) (4 7) (3 5) (2 3) (1 6)) ((8 7) (7 2) (6 4) (5 1) (4 8) (3 5) (2 3) (1 6)) ((8 5) (7 1) (6 8) (5 4) (4 2) (3 7) (2 3) (1 6)) ((8 4) (7 1) (6 5) (5 8) (4 2) (3 7) (2 3) (1 6)) ((8 5) (7 2) (6 8) (5 1) (4 4) (3 7) (2 3) (1 6)) ((8 3) (7 7) (6 2) (5 8) (4 5) (3 1) (2 4) (1 6)) ((8 3) (7 1) (6 7) (5 5) (4 8) (3 2) (2 4) (1 6)) ((8 8) (7 2) (6 5) (5 3) (4 1) (3 7) (2 4) (1 6)) ((8 3) (7 5) (6 2) (5 8) (4 1) (3 7) (2 4) (1 6)) ((8 3) (7 5) (6 7) (5 1) (4 4) (3 2) (2 8) (1 6)) ((8 5) (7 2) (6 4) (5 6) (4 8) (3 3) (2 1) (1 7)) ((8 6) (7 3) (6 5) (5 8) (4 1) (3 4) (2 2) (1 7)) ((8 5) (7 8) (6 4) (5 1) (4 3) (3 6) (2 2) (1 7)) ((8 4) (7 2) (6 5) (5 8) (4 6) (3 1) (2 3) (1 7)) ((8 4) (7 6) (6 1) (5 5) (4 2) (3 8) (2 3) (1 7)) ((8 6) (7 3) (6 1) (5 8) (4 5) (3 2) (2 4) (1 7)) ((8 5) (7 3) (6 1) (5 6) (4 8) (3 2) (2 4) (1 7)) ((8 4) (7 2) (6 8) (5 6) (4 1) (3 3) (2 5) (1 7)) ((8 6) (7 3) (6 5) (5 7) (4 1) (3 4) (2 2) (1 8)) ((8 6) (7 4) (6 7) (5 1) (4 3) (3 5) (2 2) (1 8)) ((8 4) (7 7) (6 5) (5 2) (4 6) (3 1) (2 3) (1 8)) ((8 5) (7 7) (6 2) (5 6) (4 3) (3 1) (2 4) (1 8)))
> (length (queens 8))
92