Queens Programmation Problem

[Moonlight]

I need help on how to do a programmation problem.

The problem is to place 8 queens on a chess board (8x8) and that they do not see each other.

I need to Optimize and Find all the possible solutions the following routine : (it's an algorithm)


eight-queens() {
[nbsp][nbsp]for i <- 1 to 8 do
[nbsp][nbsp][nbsp][nbsp]for j <- 1 to 8 do
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp] B[i,j] = 0
[nbsp][nbsp]eight-queens-rec(B,0)
}

eight-queens-rec(B,k) {
[nbsp][nbsp]if k == 8 then
[nbsp][nbsp][nbsp][nbsp]print B
[nbsp][nbsp][nbsp][nbsp]return
[nbsp][nbsp]for i <- 1 to 8 do
[nbsp][nbsp][nbsp][nbsp]for j <- 1 to 8 do
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]if SOLUTION(B,i,j) then
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp] B[i,j] = 1
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp] eight-queens-rec(B,k + 1)
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp] B[i,j] = 0
}


That code shows really 1 posibility, and it isn't optimized. So the task is to optimize it and to display all the posibilities.

I was thinking of the following optimization, but it only return 1 possibility.


queens (k, col, diag45, diag135) {
[nbsp][nbsp]if k == 8 then
[nbsp][nbsp][nbsp][nbsp] write sol
[nbsp][nbsp]else
[nbsp][nbsp][nbsp][nbsp] for j <- 1 to 8 do
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp] if (j not in col) and (j-k not in diag45) and (j+k not in diag135) then
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]sol[k + 1] <- j
[nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp][nbsp]queens(k+1, col union {j}, diag45 union {j-k}, diag135 union {j + k})
}


To call the above method, it's queens (0, &quot;&quot;, &quot;&quot;, &quot;&quot;). It does not return all the possibilities, just 1 of them.

What do I do to show all the possibilities?

Thanks,

Moonlight