Analysis of Algorithms : An Active Learning Approach

248 OTHER ALGORITHMIC TECHNIQUES

row = 1

repeat

// at this point we have placed queens in rows 1...row - 1

spotsPossible = 0

for i = 1 to 8 do

if location row, i is not attacked then

spotsPossible = spotsPossible + 1

if uniform(1, spotsPossible) = 1 then

try = i

end if

end if

end for

if spotsPossible > 0 then

result[row] = try

row = row + 1

end if

until spotsPossible = 0 or row = 9

return (spotsPossible > 0)

■FIGURE 9.5

A solution to the

eight queens

problem