SICP Exercise 2.43 slow queens

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.

 SOLUTION

 The code and tests are here.

Explanation
===========
In this procedure, the 'lambda (new-row)' function is applied to every element in the sequence produced by (enumerate-interval 1 board-size). But note that in the implementation of this lambda function (queen-cols (- k 1)) is evaluated. Therefore, for a given 'k' queen-cols is evaluated 'board-size' times. Now, since k itself ranges from 0 to board-size, queen-cols is evaluated a total of 'board-size raised to the power (board-size + 1)'.

For a 2x2 board, it will be 8 evaluations
For a 3x3 board, it will be 81 evaluations
For a 4x4 board, it will be 1024 evaluations
For a 5x5 board, it will be 15625 evaluations
For a 6x6 board, it will be 279936 evaluations
For a 7x7 board, it will be 5764801 evaluations
For a 8x8 board, it will be 134217728 evaluations

That is why the program runs more slowly than the version in the previous exercise. 

For the eight-queen puzzle, the implementation in the previous exercise calls queen-cols 9 times (since k ranges from 8 to 0).
Therefore, assuming that the program in exercise 2.42 solves the puzzle in time T it will take Louis's program (134217728/9)T = 14913081T to solve the eight-queens puzzle.

In my testing, the difference between the two implementations first became noticeable for a board size of 7x7 where the slower implementation took about 1.2 seconds of CPU time.

 For 8x8 it took about 22 seconds of CPU time.
For 9x9 it took 793 seconds of CPU time (about 13.2 minutes).
For 10x10 it took about 242 minutes of CPU time (about 4 hours).

 See test results in the code link above.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 2.56 differentiation rule

Image
Exercise 2.56.    Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule by adding a new clause to the  deriv  program and defining appropriate procedures  exponentiation? ,  base ,  exponent , and  make-exponentiation . (You may use the symbol  **  to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself. SOLUTION The code and tests are here .
Read more

SICP Exercise 1.28 (Miller-Rabin Test)

Exercise 1.28.    One variant of the Fermat test that cannot be fooled is called the  Miller-Rabin test  (Miller 1976; Rabin 1980). This starts from  an alternate form of Fermat's Little Theorem, which states that if  n  is a prime number and  a  is any positive integer less than  n , then  a  raised to the ( n  - 1)st power is congruent to 1 modulo  n . To test the primality of a number  n  by the Miller-Rabin test, we pick a random number  a < n  and raise  a  to the ( n  - 1)st power modulo  n  using the  expmod  procedure. However, whenever we perform the squaring step in  expmod , we check to see if we have discovered a ``nontrivial square root of 1 modulo  n ,'' that is, a number not equal to 1 or  n  - 1 whose square is equal to 1 modulo  n . It is possible to prove that if such a nontrivial square root of 1 exists, then  n  is not prime. It is also possible to prove that if  n  is an odd number that is not prime, then, for at least half the numbers a < n , co
Read more

SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.   Consider an alternative strategy for scanning out definitions that translates the example in the text to (lambda < vars >   (let ((u '*unassigned*)         (v '*unassigned*))     (let ((a < e1 >)           (b < e2 >))       (set! u a)       (set! v b))     < e3 >)) Here  a  and  b  are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the  solve  procedure from section  3.5.4 : (define (solve f y0 dt)   (define y (integral (delay dy) y0 dt))   (define dy (stream-map f y))   y) Will this procedure work if internal definitions are scanned out as shown in this exercise? What if they are scanned out as shown in the text? Explain. SOLUTION & DISCUSSION The streams based procedure 'solve' in this exercise exposed several issues in my metacircular evaluator implementation. I discovered that streams are not at all handled properly by my evaluator. Moreover, the &
Read more