SICP Exercise 2.43: Louis' Queens

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.

Here's Louis' full version of the queens procedure:

(define (queens board-size)
  (define (queen-cols k)  
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (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)))))
  (queen-cols board-size))

So what effect has interchanging the order of the nested mappings in flatmap had? Well, it still correctly constructs all of the potential positions for a queen to go in the current column. However, whereas in the original version each call to (queen-cols k) would have made only a single call to (queen-cols (- k 1)), in Louis' version each call to (queen-cols k) will result in board-size calls to (queen-cols (- k 1)).

Why is this?

Well in the original version in order to evaluate flatmap the interpreter first evaluates (queen-cols (- k 1)). flatmap then processes the resulting list by applying the nested mapping to each set of positions in the list. This nested mapping takes a set of safe positions for the previous columns, enumerates all of the possible row indexes for the board-size and then generates a new list of sets of potential positions from the set passed by appending each of these potential positions for the current column onto the passed set in turn.

In Louis' version this logic is reversed. In order to evaluate flatmap the interpreter first enumerates all of the possible row indexes for the board-size. flatmap then processes this list of row indexes, applying the nested mapping to each set of positions in the list. In this case the nested mapping takes a row index, generates all of the possible safe board positions for the previous columns and then generates a new list of sets of potential positions from the row index passed by appending it onto each of the each of the known safe positions for the previous columns in turn.

What does this mean for the run time of Louis' version?

In the original version in order to calculate the safe positions for (queens board-size) the interpreter would need to make one call to (queen-cols board-size), one to (queen-cols (- board-size 1)), and so on down to a single call to (queen-cols 0). This means that, for any given board-size, there are board-size + 1 calls to queen-cols.

In Louis version in order to calculate the safe positions for (queens board-size) the interpreter has to make one call to (queen-cols board-size), which then makes board-size calls to (queen-cols (- board-size 1)). Each of these calls in turn makes board-size calls to (queen-cols (- board-size 2)), giving a total of board-size² calls to (queen-cols (- board-size 2)). This carries on down to (queen-cols 0), which is called a grand total of board-sizeboard-size times. This increase in the number of steps required at each subsequent level gives us a geometric progression and so we can calculate the sum of this progression as:

  n
  Σ board-sizei
  i=0
= 1 - board-sizeboard-size+1
       1 - board-size

Note that we can also express the number of calls to queen-cols in the original implementation using the same denominator (i.e. 1 - board-size):

  board-size + 1
= 1 - board-size × board-size + 1
  1 - board-size  
= (1 - board-size)(board-size + 1)
            1 - board-size
= board-size + 1 - board-size2 - board-size
              1 - board-size
= 1 - board-size2
  1 - board-size

Then we can determine the ratio of calls to queen-cols that are required between the two algorithms for different board sizes by dividing the steps required for Louis algorithm by the steps required for the original algorithm:

  1 - board-sizeboard-size+1  /  1 - board-size2
       1 - board-size          1 - board-size
= 1 - board-sizeboard-size+1  ×  1 - board-size 
       1 - board-size          1 - board-size2
= 1 - board-sizeboard-size+1
      1 - board-size2

If we then make the naïve (and wildly incorrect) assumption that a single queen-cols call takes constant time then this would allow us to state that, given time T for the original algorithm, we would expect Louis' algorithm to take:

(1 - board-sizeboard-size+1)T
     1 - board-size2

It's a wildly incorrect assumption as the number of steps required to evaluate (queen-cols k) depends upon both k and board-size. However, I'm going to leave the exercise here.