Algorithms in a Nutshell

Randomized Algorithms | 305

When All Else

Fails

Because of the random nature of the trials, it is not at all guaranteed that the final

accurate result can be achieved simply by averaging over an increasing number of

independent random trials. Indeed, you may need an inordinately large number of

trials to achieve the desired estimate; instead of trying to use randomization to

determine an exact result, one should try to discover algorithms that seek an exact

answer.

Estimating the Size of a Search Tree

Two queens on a chess board threaten each other if they’re on the same row,

column, or diagonal. We say that a set of queens on a chessboard is non-threatening

if no two of them threaten each other. Clearly we can’t placen+1 non-threatening

queens on ann-by-nboard since two queens can’t share the same row. Can we

always placennon-threatening queens? This question is known as then-Queens

Problem. Let’s generalize this question a bit and count the number of ways to

placennon-threatening queens on ann-by-nboard. The randomized technique

we introduce has a number of applications beyond the game version we discuss

here; it can be used whenever we want to estimate the shape of a search tree.

There is no known efficient technique to count the number of solutions to then-

Queens Problem. Table 10-2 contains early computed values taken from Sloane’s

On-Line Encyclopedia of Integer Sequences.*

*http://www.research.att.com/~njas/sequences/A000170

Table 10-2. Known count of solutions for n-Queens Problem with our computed

estimates

n

Actual number of

solutions

Estimation with

T=1,024 trials

Estimation with

T=8,192 trials

Estimation with

T=65,536 trials

11111

20000

30000

42222

5 10101010

64544

7 40413940

8 92888793

9 352 357 338 351

10 724 729 694 718

11 2,680 2,473 2,499 2,600

12 14,200 12,606 14,656 13,905

13 73,712 68,580 62,140 71,678

14 365,596 266,618 391,392 372,699

15 2,279,184 1,786,570 2,168,273 2,289,607

16 14,772,512 12,600,153 13,210,175 15,020,881

17 95,815,104 79,531,007 75,677,252 101,664,299

18 666,090,624 713,470,160 582,980,339 623,574,560

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

Licensed by

Ming Yi