Algorithms in a Nutshell

Randomized Algorithms | 307

When All Else

Fails

the 19-Queens Problem is much harder. Since there are 4,968,057,848 nodes at

level 19 of the search tree, and the entire tree has many more nodes, we’d expect

to spend a really long time to compute the answer.

Donald Knuth (1975) developed a novel alternative approach to estimate the size

and shape of a search tree. His method corresponds to taking a random walk

down the tree. For the sake of brevity, we illustrate his technique for the 4-Queens

Problem, but clearly it could just as easily be applied to approximate the number

of solutions to the 19-Queens Problem. Starting with the root of the search tree

(no queens placed), we estimate that there is one node at that level 0. The one

operation we must do at any node is to determine the number of children of that

node (the number of direct extensions of the partial solution at that node) and

then randomly choose one of them. We see that the root node has four children,

so we estimate (correctly) that there are four nodes at that level (level1). We then

randomly choose one of those four children, let’s say the first. This corresponds to

the path in Figure 10-4.

Figure 10-3. Final solution for 4-Queens Problem with four rows extended

Figure 10-4. Random path of length 2

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