SICP Exercise 2.43

Question

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\times 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
 (λ (new-row)
   (map (λ (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\).

Answer

The exchange makes the program run much slower because now, queen-cols is called board-size times for every single iteration of flatmap. This is, of course, not ideal, since a lot of this work is duplicated. Using the original algorithm, queen-cols would generally only be called once for each iteration.

This means the algorithm now has some kind of exponential complexity. Compared to the original time \(T\), it would now take (I think) \((8^8)T\), as it is a tree-recursive algorithm.