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.

————————————————————————————————————————————————————————————————————————

Rather than calculating the rest of the board once, and then checking 
each new-row against it, Louis's program calculates new-row once and 
then recalculates the rest of the board for each.  Thus in the 8×8 case, 
the entire set of 7×8 solutions will be calculated 8 times.  The 6×8 
solutions will be calculated 8 times each time the 7×8 solutions are 
calculated.

To calculate the 1×8 solutions, we construct a set of all possibilities 
and check them all.  This is the same in Louis's program.

To calculate the 2×8 solutions, Louis's program constructs all the 1×8 
solutions again 8 times, and then does the same tests we do.  In our 
solution the 1x8 solutions are not calculated again, so this is 8 times 
slower.

To calculate the 3×8 solutions, Louis's program finds all the 2×8 
solutions again, 8 times, so this will take 64 times as long.

The 4×8 solutions will take 8³ times as long, and the full set of 8×8 
solutions will take 8⁷ times as long.