SICP 問題 2.43

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

(define (l-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))

元のqueensではqueen-colsはboard-size回呼ばれている．
それがLouisのqueensでは(new-row k)一個につき1回呼ばれている．
つまり　border-size = xとして
1 + x^1 + x^2 + ... x^(x-1) = (x^x - 1)/ (x - 1)回呼ばれている．
よってLouisのqueensがかかる時間は　T * ((x^x - 1/ (x * (x - 1)))．