pivot( T[i..j], l )
// permutes the elements in array T[i..j] and returns a value l such
// that , at the end, i <=l <=j, T[k] <= p for all i <=
k < l, T[l] = p, and
// T[k] > p for all l < k <= j, where p is the initial value
of T[i]
p = T[i]
k = i; l = j + 1
repeat k = k + 1 until T[k] > p or k >= j
repeat l = l - 1 until T[l] <= p
while k < l do
swap T[k] and T[l]
repeat k = k + 1 until T[k] >
p
repeat l = l -1 until T[l] <=
p
swap T[i] and T[l]
queens( k, col, diag45, diag135 )
// sol[1..k] is k-promising
// col = { sol[i] | 1 <= i <= k }
// diag45 = { sol[i] - i + 1 | 1 <= i <= k }
// diag135 = { sol[i] + i - 1 | 1 <= i <= k }
if k = 8 then // an 8-promising vector is
a solution
write sol
else // explore (k+1)-promising vectors of
sol
for j = 1 to 8 do
if j
not-in col and j-k not-in diag45 and j+k not-in diag135
then
sol[k+1] = j // sol[1..k+1] is (k+1)-promising
queens( k+1, col u {j}, diag45 u {j-k}, diag135
u {j+k} )
queenLV( sol[1..8], success)
array ok[1..8] // available positions
col, diag45, diag135 = empty
for k = 0 to 7 do
// sol[1..k] is k-promising, place the (k+1) th queen
nb = 0 // count the number
of possibilities
for j = 1 to 8 do
if j not-in col and j-k not-in
diag45 and j+k not-in diag135
then // column j is available
for the (k+1) th queen
nb =
nb - 1
ok[nb]
= j
if nb
= 0 then return success = false
j = ok[uniform(1..nb)]
col =
col u {j}
diag45
= diag45 u { j - k }
diag135
= diag135 u { j + k }
sol[
k + 1] = j
return success = true