9.2 PROBABILISTIC ALGORITHMS 249Let’s look at what this algorithm is doing. The repeat loop will take us through
each of the eight rows on the board. For each of these rows, we look at each
column location, and if it isn’t attacked, we increment spotsPossible. The
nextif statement looks a little strange, but watch what happens when we
move down the first row in which no spaces are attacked. For the first column,
uniform generates a number between 1 and 1, which must be 1, so try gets
set to the first column. For the second column, uniform generates a number
between 1 and 2, which has a 50% chance of being 1, so there is a 50% chance
thattry will be changed to 2. For the third column, uniform generates a
number between 1 and 3, which has a 33% chance of being 1, so there is a
33% chance that try will be changed to 3. For the fourth column, uniform
generates a number between 1 and 4, which has a 25% chance of being 1, so
there is a 25% chance that try will be changed to 4. The end result is that each
of the free columns will have the chance of 1 / spotsPossible of being the
one tried on this pass. We do this again for the rest of the rows. This repeats
until either spotsPossible is zero because there are no unattacked locations
orrows is nine because we filled all of the rows. In the first case, this algo-
rithm stops and indicates failure. In the second case, we solved the eight
queens problem and return true.
A full statistical analysis discovers that the probability of success is about
0.1293, and the number of passes for a failure is about 6.971. Using the equa-
tion above, we find that this algorithm will take about 55 passes. If we looked
at an analysis of the recursive version of the eight queens problem, you would
see that it takes more than twice as many passes.
■ 9.2.4 Sherwood Algorithms
Sherwood algorithms always give an answer, and the answer is always correct.
These algorithms are applied to situations where the best, average, and worst
cases for a deterministic algorithm differ significantly. Sherwood algorithms
introduce randomness to help move the complexity of the deterministic algo-
rithm from the extremes of its worst and best cases.
An example of this would be the choice of the pivot element for quicksort.
In the analysis of that algorithm, we pointed out that the worst case would be
if the list was already sorted because each time we would pick the smallest ele-
ment for the pivot. If instead, we randomly picked the pivot element between
first and last, we would lessen the chance of the worst case occurring. We
would not eliminate that chance, because we could randomly pick the smallest