SICP Exercise 2.43: Eight queens: interchange the order of the nested mappings

"Life is all about sharing. If we are good at something, pass it on." - Mary Berry

SICP Exercise 2.43: Eight queens: interchange the order of the nested mappings

2021-11-02

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
1                 (flatmap
2                     (trace-lambda (new-row)
3                         (map (lambda (rest-of-queens)
4                                 (adjoin-position new-row k rest-of-queens))
5                              (queen-cols (- k 1))))
6                     (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.

The procedure in 2.42:

 1     (trace-define (queen-cols k)
 2         (if (= k 0)
 3             (list empty-board)
 4             (filter
 5                 (lambda (positions) (safe? k positions))
 6                 (flatmap
 7                     (lambda (rest-of-queens)
 8                         (map (trace-lambda (new-row)
 9                                 (adjoin-position new-row k rest-of-queens))
10                              (enumerate-interval 1 board-size)))
11                     (queen-cols (- k 1))))))

So, for each column k, (queen-cols (- k 1)) is called only one time:

 1$ racket 2.42-eight-queens.rkt 4
 2>(queen 4)
 3>(queen-cols 4)
 4> (queen-cols 3)
 5> >(queen-cols 2)
 6> > (queen-cols 1)
 7> > >(queen-cols 0)
 8< < <'(())
 9< < '(((1 1)) ((2 1)) ((3 1)) ((4 1)))
10< <'(((3 2) (1 1))
11     ((4 2) (1 1))
12     ((4 2) (2 1))
13     ((1 2) (3 1))
14     ((1 2) (4 1))
15     ((2 2) (4 1)))
16< '(((2 3) (4 2) (1 1))
17    ((1 3) (4 2) (2 1))
18    ((4 3) (1 2) (3 1))
19    ((3 3) (1 2) (4 1)))
20<'(((3 4) (1 3) (4 2) (2 1)) ((2 4) (4 3) (1 2) (3 1)))
21'(((3 4) (1 3) (4 2) (2 1)) ((2 4) (4 3) (1 2) (3 1)))

In 2.43, since the order of the nested mappings has interchanged:

 1    (trace-define (queen-cols k)
 2        (if (= k 0)
 3            (list empty-board)
 4            (filter
 5                (lambda (positions) (safe? k positions))
 6                (flatmap
 7                    (trace-lambda (new-row)
 8                        (map (lambda (rest-of-queens)
 9                                (adjoin-position new-row k rest-of-queens))
10                             (queen-cols (- k 1))))
11                    (enumerate-interval 1 board-size)))))

For each column k, (queen-cols (- k 1)) is called board-size times:

 1$ racket 2.43-eight-queens-interchange-order.rkt 4
 2>(queen 4)
 3>(queen-cols 4)
 4> (queen-cols 3)
 5> >(queen-cols 2)
 6> > (queen-cols 1)
 7> > >(queen-cols 0)
 8< < <'(())
 9> > >(queen-cols 0)
10< < <'(())
11> > >(queen-cols 0)
12< < <'(())
13> > >(queen-cols 0)
14< < <'(())
15< < '(((1 1)) ((2 1)) ((3 1)) ((4 1)))
16> > (queen-cols 1)
17> > >(queen-cols 0)
18< < <'(())
19> > >(queen-cols 0)
20< < <'(())
21> > >(queen-cols 0)
22< < <'(())
23> > >(queen-cols 0)
24< < <'(())
25< < '(((1 1)) ((2 1)) ((3 1)) ((4 1)))
26> > (queen-cols 1)
27> > >(queen-cols 0)
28< < <'(())
29> > >(queen-cols 0)
30< < <'(())
31> > >(queen-cols 0)
32< < <'(())
33> > >(queen-cols 0)
34< < <'(())
35< < '(((1 1)) ((2 1)) ((3 1)) ((4 1)))
36> > (queen-cols 1)
37> > >(queen-cols 0)
38< < <'(())
39> > >(queen-cols 0)
40< < <'(())
41> > >(queen-cols 0)
42< < <'(())
43> > >(queen-cols 0)
44< < <'(())
45< < '(((1 1)) ((2 1)) ((3 1)) ((4 1)))
46< <'(((1 2) (3 1))
47     ((1 2) (4 1))
48     ((2 2) (4 1))
49     ((3 2) (1 1))
50     ((4 2) (1 1))
51     ((4 2) (2 1)))
52 ...

1$ for size in (seq 3 6); echo -n $size": "; racket 2.43-eight-queens-interchange-order.rkt $size | grep -c 'queen-cols 0'; end
23: 27 = 3^3
34: 256 = 4^4
45: 3125 = 5^5
56: 46656 = 6^6

So, if the program in 2.42 solves the eight-queens puzzle in time T, 2.43’s version will take roughly T⁷ to complete.

Tags: sicp scheme

Edit on GitHub