SICP中包含了一个n皇后问题的部分解决方案。该方案通过遍历每一行可能的皇后位置的树形结构,生成下一行更多的可能位置来结合到目前为止的结果,对可能性进行过滤以保留只有最新的皇后是安全的选项,并递归重复这个过程。但是这种策略在n等于11时会出现最大递归错误。
我实现了一种智能的方法,从第一列开始进行更为高效的树形遍历,从未使用过的行列表中生成可能的位置,将每个位置列表连接到更新的未使用行列表中。然后对被认为是安全的配对进行过滤,并递归地映射到下一列。这种方法不会崩溃(至少迄今为止还没有),但n等于12时需要一分钟,n等于13时需要约10分钟才能解决。
我实现了一种智能的方法,从第一列开始进行更为高效的树形遍历,从未使用过的行列表中生成可能的位置,将每个位置列表连接到更新的未使用行列表中。然后对被认为是安全的配对进行过滤,并递归地映射到下一列。这种方法不会崩溃(至少迄今为止还没有),但n等于12时需要一分钟,n等于13时需要约10分钟才能解决。
(define (queens board-size)
(let loop ((k 1) (pp-pair (cons '() (enumerate-interval 1 board-size))))
(let ((position (car pp-pair))
(potential-rows (cdr pp-pair)))
(if (> k board-size)
(list position)
(flatmap (lambda (pp-pair) (loop (++ k) pp-pair))
(filter (lambda (pp-pair) (safe? k (car pp-pair))) ;keep only safe
(map (lambda (new-row)
(cons (adjoin-position new-row k position)
(remove-row new-row potential-rows))) ;make pp-pair
potential-rows)))))))
;auxiliary functions not listed
我并不是在寻找代码,而是需要解释一下一种或两种策略,让其更加符合函数式编程的思想,并且易于理解。
mit-scheme --stack <number-of-1024-blocks>
命令。我知道,这并没有回答你的算法问题。 - GoZoner