#include "MPQueue.h"
#include <deque>
using namespace std;

enum { NONE, PLACE, RESULT };
typedef vector < int > Trow;
unsigned long int allsolutions = 0;             // total number solutions
int overflow = 50;                              // controlls local queue size
const int size = 16;                            // size of the board

bool inline fits (const Trow & row) {
  int j = row.size () - 1;
  for (int i = 0; i < j; i++)
    if ( ( row[i] == row.back () ) || ( abs (row[i] - row[j]) == j - i ) )
      return false;                             // queens interfere
  return true;                                  // last queen fits
}

void MPQswitch (Tjob & job) {
  Trow row;                                     // a partial placement
  deque < Trow > rows;                          // local job queue
  unsigned int solutions = 0;                   // local number of solutions
  switch (job.type) {
  case PLACE:                                   // add queen in next column
    from_string (row, job.data);
    rows.push_back (row);                 	// populate a local job queue 
    while (!rows.empty ()) {              	// still local jobs to do
      row = rows.back ();                     
      rows.pop_back ();
      for (row.push_back (0); row.back () < size; row.back ()++)
	if (fits (row))                         // does the new queen fit? 
	  if (row.size () == size)              // all queens added
	    solutions++;                        // found a new solution
	  else {
	    rows.push_back (row);               // add to local job queue
	    if (rows.size () > overflow) {      // if too many local jobs 
	      MPQsubmit (Tjob(PLACE, rows.front ())); // send one to the boss
	      rows.pop_front ();
	    }
	  }
    }
    job = Tjob(RESULT, solutions);              // prepare the result
    MPQtask (job);          			// send result to the boss
    break;
  case RESULT:
    from_string (solutions, job.data);          // update total solutions
    allsolutions += solutions;                  // with new result
    job.data = "";                              // no result to return 
  }
}

int main (int argc, char *argv[]) {
  MPQinit (argc, argv);
  MPQstart ();
  Tjobqueue inqueue, outqueue;
  inqueue.push (Tjob(PLACE, Trow ()));         // initial empty placement
  MPQrunjobs (inqueue, outqueue);
  cout << allsolutions << " solutions\n";
  MPQstop ();
}