## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.43

## Problem

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 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*.

## Solution

The original version of the `flatmap` expression evaluates the combination
`(queen-cols (- k 1))` once, and evaluates the `enumerate-interval`
expression *once for each element* in the sequence generated by
evaluating `(queen-cols (- k 1))`. By flipping the order of the nested mappings,
Louis's version of the expression evaluates the
`enumerate-interval` expression once and evaluates `(queen-cols (- k
1))` `board-size` times, once for each number in the sequence
generated by the `enumerate-interval` expression.

`enumerate-interval` is a simple linear-recursive procedure, so it's
relatively cheap to evaluate the expression `(enumerate-interval 1 board-size)`
multiple times. Computing `queen-cols` is more expensive, if for no
other reason than the fact that evaluating `queen-cols` also
evaluates `(enumerate-interval 1 board-size)`.

The original version of the `queen-cols` procedure generates a linear-recursive process, but Louis's version generates a tree-recursive
process, so the original version is going to be appreciably faster than
Louis's for large enough values of board-size.

Now let's address the second part of the exercise: if the original
version of the procedure takes time *T* to solve the eight-queens puzzle,
how long does it take Louis's version?

The tree-shaped process generated by evaluating Louis's version of
`queens` has degree `board-size`, i.e., each non-leaf node in the tree
has `board-size` children. Each node also decrements *k*, the number
of columns being considered, until it reaches zero; *k'*s initial
value is `board-size`, so that means this version of `queens` generates
a tree-shaped process of degree `board-size` and depth `board-size`.

The number of nodes in a tree of degree *n* and depth *m* is the sum
. (Prove this to yourself by drawing
binary and ternary trees of various depths.) Therefore, evaluating
`(queens 8 )` with Louis's version of `queens` evaluates `queen-cols` 2396745 times. The original version of `queens` evaluates `queen-cols` only 8 times.

This doesn't tell the whole story about how much faster the
original version is than Louis's version. Because the sequences
generated by `(queen-cols x)` and `(queen-cols y)` for are
generally different lengths, the cost of filtering them is
different: in other words, if the original version of of `queens` takes
time *T* to solve for 8 queens, it doesn't necessarily take time *T*/2
to solve for four.

We *can* say that because the original version is linear-recursive,
the cost of evaluating it is . The cost of evaluating Louis's
version is . So if the time needed by the original version
to solve the 8 queens puzzle is *T*, we can expect the time required
for Louis's version to be roughly *T*^{7}.