// 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]
pivot( T[i..j], l )
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]
// backtrack queen
// 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 }
queens( k, col, diag45,
diag135 )
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} )
// now Las Vegas 8-queen
queenLV( sol[1..8])
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 fail
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
last update 26 Nov 2010