Algorithms in a Nutshell

(^306) | Chapter 10: When All Else Fails
To count the number of exact solutions to the 4-Queens Problem, we expand a
search tree based upon the fact that each solution will have one queen on each
row. Starting with a partial solution of having 0 queens placed, Figure 10-1 shows
how there will be a direct extension corresponding to each of the four placements
of a queen on the first row.
Extending each of these partial solutions by all non-threatening placements of a
queen on the second row yields Figure 10-2.
The first and last partial solutions cannot be extended by placing a queen on the
third row. The middle four can be extended to the third row, and of these, the
middle two can each be extended to a solution that includes all four rows. (See
Figure 10-3.)
Such an exhaustive elaboration of the search tree permits us to see that there are two
solutions to the 4-Queens Problem. Trying to compute the number of solutions to
19 4,968,057,848 4,931,587,745 4,642,673,268 4,931,598,683
20 39,029,188,884 17,864,106,169 38,470,127,712 37,861,260,851
Figure 10-1. Initial search tree for 4-Queens Problem
Figure 10-2. Extended search tree for 4-Queens Problem with two queens placed
Table 10-2. Known count of solutions for n-Queens Problem with our computed
estimates (continued)
n
Actual number of
solutions
Estimation with
T=1,024 trials
Estimation with
T=8,192 trials
Estimation with
T=65,536 trials
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