*
* README 9.1 92/07/01 16:40:21
*

examples/c/nqueens

The nqueens program is an example of manager/worker decomposition.

The problem is stated as follows:  Given an nxn chess board, where
can you place n queens such that each queen is safe form capture?

This program has been tested for an 8x8 board with 8 queens and four
nodes.

This problem is typical of problems for which there is no
analytical solution.  Instead, there exist a large number of
candidate solutions.  You test each solution and accept those 
that pass.

You can arrange the possibilities into a solution tree.  Some
solutions lie near the root of the tree.  Others are deep into
the tree.  If you assign each node a start point in the tree, 
some nodes are going to finish early and wait for other nodes.
This results in bad load balancing.

Manager/worker decomposition deals with that imbalance by dividing 
the problem into a large number of tasks (greater than the
number of nodes).  The tasks range in complexity.  The manager
assigns a task to each node.  When a node completes its task, it
requests more work from the manager, and the manager assigns it
another task.

In this example node 0 is the manager.  Node 0 creates partially
filled boards and passes them on to individual nodes.  Node 0
populates the first two columns on the board (this is a constant
called MCOLS).  Node 0 will not put two queens in the same column,
but other than that, it makes no attempt to check the boards.
When MCOLS is 2 node 0 creates 64 boards.

Some of the boards are immediately rejected by the nodes.  
For example, a board with two queens in the same row is rejected.
Other boards require testing by the node.  The compute node 
assigned a partial board recusively tests solutions for the rest of
the board.  When it finds a solution, it writes it to a CFS file
called queens.out and requests another board from the manager.  	

The file was opened in CFS mode 1.  In this mode the nodes 
write the file on a first-come first-served basis.
The result is that the file contains the solutions as they were
found by the nodes.  Finally, node 0, performs a global
sum and prints the total number of solutions.

For the 8 queens problem, there are 92 solutions.