Algorithms in a Nutshell

(^308) | Chapter 10: When All Else Fails
To the lower node of the current random path, we apply the operation of deter-
mining how many children it has (in how many ways can a non-threatening queen
be placed on the second row?), and then randomly choose one of them. Noting
that there are two children, we estimate that the number of nodes at the next level
is two times the estimate of the number of nodes at level 1. That is, we estimate
that there are eight nodes at level 2, and we extend our current path by randomly
choosing one of the two children at the bottom of the current path, as shown in
Figure 10-5.
Now, to the lowest node of the current random path, we apply the operation of
determining how many children it has: in how many ways can a non-threatening
queen be placed on the third row? Noting that there are 0 ways, we estimate that
the number of nodes at the next level is 0 times the estimate of the number of
nodes at level 2. That is, we estimate that there are 0*8 nodes at level 3, and hence
0 nodes at level 4. This implies that we estimate that there are 0 solutions to the 4-
Queens Problem. In fact some of the random walks will lead to overestimates, and
if we do many random walks and average the estimates, we expect to get closer
and closer to the true value. And since each estimate can be computed quickly,
this refined (averaged) estimate can also be computed quickly. The expected value
of each estimate is the correct value, but the likelihood of the average of a number
of estimates being close to the true answer increases as the number of trials being
averaged increases. If you refer back to Table 10-2, we show the computed results
from our implementation for 1,024, 8,192, and 65,536 trials. No timing informa-
tion is included, because all results were computed in less than a minute. The final
estimate for the 19-Queens problem with T=65,536 trials is within 3% of the
actual answer. Indeed, all of the estimations for T=65,536 are within 5.8% of the
actual answer. This algorithm has the desirable property that the computed value
is more accurate as more random trials are run. Example 10-2 shows the imple-
mentation in Java for a single computation of then-Queens estimation. The full
code that generated Table 10-2 is available in the repository.
Figure 10-5. Random path of length 3
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use