"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

Categories:

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)
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)
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)
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 T7 to complete.

Tags:

Related Posts: