The N-Queens problem


In the N Queens problem the object is to place N queens on a chessboard in 
such a way that no queens can capture a piece. 
This means that no two queens may be placed on the same row, column, or diagonal.

For example if N=4 :

---------
| |X| | |
---------
| | | |X|
---------
|X| | | |
---------
| | |X| |
---------
  Right

---------
| |X| | |
---------
| | | |X|
---------
| | |X| |
---------
|X| | | |
---------
  Wrong

  Some linear algorithms exists to generate one solution. But as the objective
is to compute the number of solutions and the whole set of solutions,
we need to do a tree search.

For each row, we try to add a queen by checking the occupied columns and
diagonals. When a queen is placed, we do the same for the next row.
If no queen can be placed in a row, we go back and move the preceding
queen. If N queen have been placed, we have obtained a solution. We 
save this solution and continue the algorithm.
  If we try to go back in the first row that mean that we have reached
the end.

  The implementation of the algorithm use bitmasks to check the
occupied columns and diagonals. The diagonals masks are shifted
at each operation. All this masks are compacted in a single word
to decrease the number of memory access (the masks are stacked).

The algorithm at work with N=4:

  0 1 2 3
 ---------
0| |X| | |
 ---------
1| | | |X|
 ---------
2| | |X| |
 ---------
3|X| | | |
 ---------

The coordinates are (row,col).

(0,0) : free -> place a queen
(1,0) : occupied
(1,1) : occupied
(1,2) : free -> place a queen
(2,0) : occupied
(2,1) : occupied
(2,2) : occupied
(2,3) : occupied
All this row is occupied, we go back :
(1,3) : free -> place a queen
...

The parallel algorithm :
-------------------------

The goal is now to distribute the load between several processors.
The idea is to generate a list of task and as soon as a processor
has finished its assigned work, it search another task.
Each task will be "own" by a processor to distribute also the 
load of searching a task.