Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
167 lines (152 sloc) 3.98 KB

##2.42

经典的八皇后问题,不过比较好的地方是这个题目给出了程序的大致骨架,我们需要实现的只是一些构造函数与选择函数而已。

我这里用一个list表示一种解法,比如四皇后问题,解法(A B C D)表示,第一个皇后在位置A,第二个皇后在位置B,第三个皇后在位置C,第四个皇后在位置D,用list的位置表示了皇后的次序。

在前面已经放置了n-1个皇后的基础上,判断第n个皇后是否合法的做法是:

先把n-1个皇后的解法的list倒转过来,然后依次判断第n个皇后与前面n-1的位置关系。

我这里把list倒转过来,是为了方便判断45度方向上是否合法。

(load "2.17_2.18.scm")
(load "2.40.scm")
(define (enumerate-interval n)
    (if (< n 1)
      nil
      (append (enumerate-interval (- n 1))
              (list n))))
              
(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 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

(define empty-board ())

(define (adjoin-position new-row k rest-of-queens)
  (append rest-of-queens (list new-row)))

(define (ok? v pos offset)
    (cond
      ((null? pos) #t)
      ((and (not (= v (car pos)))
             (not (= v (- (car pos) offset)))
             (not (= v (+ (car pos) offset))))
        (ok? v (cdr pos) (+ 1 offset)))
      (else #f)))

(define (safe? k positions)
  (let ((rev_positions (reverse positions)))
    (ok? (car rev_positions) (cdr rev_positions) 1)))

(queens 8)
;Value: 一共92个解
((1 5 8 6 3 7 2 4)
(1 6 8 3 7 4 2 5)
(1 7 4 6 8 2 5 3)
(1 7 5 8 2 4 6 3)
(2 4 6 8 3 1 7 5)
(2 5 7 1 3 8 6 4)
(2 5 7 4 1 8 6 3)
(2 6 1 7 4 8 3 5)
(2 6 8 3 1 4 7 5)
(2 7 3 6 8 5 1 4)
(2 7 5 8 1 4 6 3)
(2 8 6 1 3 5 7 4)
(3 1 7 5 8 2 4 6)
(3 5 2 8 1 7 4 6)
(3 5 2 8 6 4 7 1)
(3 5 7 1 4 2 8 6)
(3 5 8 4 1 7 2 6)
(3 6 2 5 8 1 7 4)
(3 6 2 7 1 4 8 5)
(3 6 2 7 5 1 8 4)
(3 6 4 1 8 5 7 2)
(3 6 4 2 8 5 7 1)
(3 6 8 1 4 7 5 2)
(3 6 8 1 5 7 2 4)
(3 6 8 2 4 1 7 5)
(3 7 2 8 5 1 4 6)
(3 7 2 8 6 4 1 5)
(3 8 4 7 1 6 2 5)
(4 1 5 8 2 7 3 6)
(4 1 5 8 6 3 7 2)
(4 2 5 8 6 1 3 7)
(4 2 7 3 6 8 1 5)
(4 2 7 3 6 8 5 1)
(4 2 7 5 1 8 6 3)
(4 2 8 5 7 1 3 6)
(4 2 8 6 1 3 5 7)
(4 6 1 5 2 8 3 7)
(4 6 8 2 7 1 3 5)
(4 6 8 3 1 7 5 2)
(4 7 1 8 5 2 6 3)
(4 7 3 8 2 5 1 6)
(4 7 5 2 6 1 3 8)
(4 7 5 3 1 6 8 2)
(4 8 1 3 6 2 7 5)
(4 8 1 5 7 2 6 3)
(4 8 5 3 1 7 2 6)
(5 1 4 6 8 2 7 3)
(5 1 8 4 2 7 3 6)
(5 1 8 6 3 7 2 4)
(5 2 4 6 8 3 1 7)
(5 2 4 7 3 8 6 1)
(5 2 6 1 7 4 8 3)
(5 2 8 1 4 7 3 6)
(5 3 1 6 8 2 4 7)
(5 3 1 7 2 8 6 4)
(5 3 8 4 7 1 6 2)
(5 7 1 3 8 6 4 2)
(5 7 1 4 2 8 6 3)
(5 7 2 4 8 1 3 6)
(5 7 2 6 3 1 4 8)
(5 7 2 6 3 1 8 4)
(5 7 4 1 3 8 6 2)
(5 8 4 1 3 6 2 7)
(5 8 4 1 7 2 6 3)
(6 1 5 2 8 3 7 4)
(6 2 7 1 3 5 8 4)
(6 2 7 1 4 8 5 3)
(6 3 1 7 5 8 2 4)
(6 3 1 8 4 2 7 5)
(6 3 1 8 5 2 4 7)
(6 3 5 7 1 4 2 8)
(6 3 5 8 1 4 2 7)
(6 3 7 2 4 8 1 5)
(6 3 7 2 8 5 1 4)
(6 3 7 4 1 8 2 5)
(6 4 1 5 8 2 7 3)
(6 4 2 8 5 7 1 3)
(6 4 7 1 3 5 2 8)
(6 4 7 1 8 2 5 3)
(6 8 2 4 1 7 5 3)
(7 1 3 8 6 4 2 5)
(7 2 4 1 8 5 3 6)
(7 2 6 3 1 4 8 5)
(7 3 1 6 8 5 2 4)
(7 3 8 2 5 1 6 4)
(7 4 2 5 8 1 3 6)
(7 4 2 8 6 1 3 5)
(7 5 3 1 6 8 2 4)
(8 2 4 1 7 5 3 6)
(8 2 5 3 1 7 4 6)
(8 3 1 6 2 5 7 4)
(8 4 1 3 6 2 7 5))

##2.43

Louis Reasoner的flatmap如下:

(flatmap
  (lambda(new-row)
    (map
      (lambda(rest-of-queens)
        (adjoin-position new-row k rest-of-queens))
      (queen-cols (- k 1))))
  (enumerate-interval board-size))

这里把queens-cols这个树形递归放到了map里面,这样相当于每次求(queens n)时,都会求n次(queens (- n 1)),也就是说

每次递归调用时,是之前计算量的n倍,又因为一共有n次递归调用,所以总的计算时间是之前的n2倍。