练习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))