Exercise 2.43 · 习题

Exercise 2.43: Louis Reasoner is having a
terrible time doing Exercise 2.42. His queens procedure seems to
work, but it runs extremely slowly. (Louis never does manage to wait long
enough for it to solve even the 6
×
6 case.) When Louis asks Eva Lu Ator for
help, she points out that he has interchanged the order of the nested mappings
in the flatmap, writing it as

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

Explain why this interchange makes the program run slowly. Estimate how long

it will take Louis’s program to solve the eight-queens puzzle, assuming that

the program in Exercise 2.42 solves the puzzle in time T.

练习 2.43：Louis Reasoner 在做练习 2.42 时遇到了很大麻烦。他的 queens 过程似乎能运行，但运行得极其缓慢。（Louis 从来没有等到它解出 6 × 6 的情况。）当 Louis 向 Eva Lu Ator 求助时，她指出他交换了 flatmap 中嵌套映射的顺序，将其写成了

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

请解释为什么这种交换会使程序运行得很慢。假设练习 2.42 中的程序解决八皇后谜题所需时间为 T，估计 Louis 的程序解决该谜题所需的时间。