【SICP练习】71 练习2.42



练习2.42

这道题曾经在C#中写过，但是写出来的代码却没有Lisp中的朴素。用了一大堆的数组和for循环。但是在这里，用car、cdr来构造就行了。

我们按书中给出的步骤来一步一步求解这个问题。首先是棋局，就按书上的示意图，从上往下的来排皇后的位置。诸如此时书中皇后的位置为：’(6 3 1 7 5 8 2 4)。

然后就是过程adjoin-position。rest-of-queens是在前k-1列放置k-1个皇后的一种方式，new-row是在第k列放置所考虑的编号。因此这一过程定义为：

(define (adjoin-position k new-rowrest-of-queens)

   (cons new-row rest-of-queens))

因为书上出现了k，我们就象征性的将k作为一个参数好了。像这种一行的代码在前面遇见过很多次了。cons就代表则构造了吧。

空棋盘则用‘()表示。因此定义如下：

(define empty-board ‘())

接下来就是这道题中的关键了，safe?。看到棋局的样子不用想也知道用迭代了吧。

(define (safe? k position)

   (define (safe?-iter row-of-new-queen rest-of-queens i)

        (if (null? rest-of-queens)

           
#t

            
(let ((row-of-current-queen (carrest-of-queens)))

               
(if (or (= row-of-new-queenrow-of-current-queen)

                     
(= row-of-new-queen (-row-of-current-queen i))

                     
(= row-of-new-queen (+row-of-current-queen i)))

                   
#t

          
         (safe?-iter row-of-new-queen (cdrrest-of-queens) (+ i 1))))))

   (safe?-iter (car position) (cdr position) 1))