sicp-ex-2.43


<< Previous exercise (2.42) | Index | Next exercise (2.44) >>

jpath

Exchanging the order of the mapping in the flatmap results in queen-cols being re-evaluated for every item in (enumerate-interval 1 board-size). Therefore the whole work has to be duplicated board-size times at every recursion level. Since there are always board-size recursions this means that the whole work will be duplicated bord-size^board-size times.

Therefore if the function would take T time to run for board-size=8 with correct ordering, with the interchanged ordering it will take (8^8)T to run.


aQuaYi.com

In 2.42, every round minus 1. so it is (n!).

In 2.43, every round is n. so it is (n^n).

for board-size=8, (8^8)/(8!)≈416T


thongpv87

@aQuaYi I don't think it is correct because number of queen-cols also change over time


woofy

Not solved yet but share my thinking process:

Q(k): number of solutions of board size n * k

T(k): number of steps required to calculate Q(k)

original approach: T(k) = T(k-1) + n * Q(k-1)

T(0) = 1

louis's approach: T(k) = n * (T(k-1) + Q(k-1)) = n * T(k-1) + n * Q(k-1)

T(0) = 1

So louis's approach requires signifcantly more steps. How many more? It's tempted to say a factor of N^N due to tree recursion but it may not be the actual case.

Found this analysis for reference: https://wernerdegroot.wordpress.com/2015/08/01/sicp-exercise-2-43/