//
//      Distributed NQueens with symmetries, Part I V. 0.01 - 17-November-2008
//
using System;

public class Task   {

 public int backtrack;
 public int left, down, right;
 public int BOUND1, BOUND2;
 public int LASTMASK, ENDBIT;

 public Task ( int backtrack, int left, int down, int right, int BOUND1,
               int BOUND2, int LASTMASK, int ENDBIT                     ) {

  this.backtrack = backtrack;
  this.left      = left;
  this.down      = down;
  this.right     = right;
  this.BOUND1    = BOUND1;
  this.BOUND2    = BOUND2;
  this.LASTMASK  = LASTMASK;
  this.ENDBIT    = ENDBIT;

 }

}

//**************************************************//

public class NQueens   {

 public static long totalCOUNT8 = 0;

 public static void Main ( String[] args ) {

  int   N  = System.Convert.ToInt32 ( args [ 0 ] ); // Board size
  int   M1 = System.Convert.ToInt32 ( args [ 1 ] ); // Number of fixed queens for 1st backtrack
  int   M2 = System.Convert.ToInt32 ( args [ 2 ] ); // Number of fixed queens for 2nd backtrack
  int   P  = System.Convert.ToInt32 ( args [ 3 ] ); // Number of workers

  NQueens nqueens = new NQueens();

  nqueens.launchWorkers ( N, M1, M2, P, nqueens.getTask, nqueens.sendStop, nqueens );

  nqueens.generateTasks ( N, M1, M2, P, nqueens.sendTask );

  for ( int i = 0; i < P; i++ )
   nqueens.getStop ? ();

  long TOTAL = totalCOUNT8 * 8;

  Console.Write     ( "Task challenge : " + N + "   " );
  Console.WriteLine ( "Solutions : COUNT8 = " + totalCOUNT8 );
  Console.WriteLine ( "Total number of solutions = " + TOTAL );

 }

 //******************************************************************************//

 public handler getTask Task(long COUNT8 ) & channel sendTask ( Task task ) {

  totalCOUNT8 += COUNT8;
  return ( task );

 }

 //******************************************************************************//

 public handler getStop void() & channel sendStop () {
  return;
 }

 //******************************************************************************//

 public async launchWorkers ( int N, int M1, int M2, int P, handler Task(int) getTask,
                              channel () sendStop, NQueens nqueens                    ) {

  for ( int i = 0; i < P; i++ )
   nqueens.Worker ( i, N, M1, M2, getTask, sendStop );

 }

 //******************************************************************************//

 public void generateTasks ( int N, int M1, int M2, int P, channel (Task) sendTask ) {

  int   BOUND1;

  int   bit;

  int   MASK  = ( 1 << N ) - 1;

  for ( BOUND1 = 2; BOUND1 < 25; BOUND1++ )   {   // BOUND1 = 2,3, ... , 24

   bit = 1 << BOUND1;

   MainBacktrack1 ( 2, ( 2 | bit ) << 1, 1 | bit, bit >> 1, BOUND1, MASK, M1, sendTask );

  }

  Task finish_marker = new Task ( -1, -1, -1, -1, -1, -1, -1, -1 );

  for ( int i = 0; i < P; i++ )
   sendTask ! ( finish_marker );

 }

 //********************************************************************************//

 public void MainBacktrack1 ( int y, int left, int down, int right, int BOUND1, int MASK,
                             int M1, channel (Task) sendTask                             ) {

  int   bitmap, bit;

  if ( y == M1 )
   sendTask ! ( new Task ( 1, left, down, right, BOUND1, -1, -1, -1 ) );
  else   {

   bitmap = MASK & ~ ( left | down | right );

   if ( y < BOUND1 ) {
    bitmap = bitmap | 2;
    bitmap = bitmap ^ 2;
   }

   while ( bitmap != 0 )   {

    bit   = -bitmap & bitmap;
    bitmap = bitmap ^ bit;

    MainBacktrack1 ( y + 1, ( left | bit ) << 1, down | bit, ( right | bit ) >> 1,
                    BOUND1, MASK, M1, sendTask                                    );

   }

  }

 }

 //********************************************************************************//

 movable Worker ( int myNumber, int N, int M1, int M2,
                  handler Task(int) getTask, channel () sendStop ) {

  int    MASK  = ( 1 << N ) - 1;

  long   COUNT8 = 0;

  Task   task  = (Task) getTask ? ( COUNT8 );

  while ( task.backtrack != -1 )   {

   if ( task.backtrack == 1 )
    WorkerBacktrack1 ( M1, task.left, task.down, task.right, task.BOUND1, MASK, N, ref COUNT8 );

   task   = (Task) getTask ? ( COUNT8 );
   COUNT8 = 0;

  }

  sendStop ! ();

 }

 //********************************************************************************//

 public void WorkerBacktrack1 ( int y, int left, int down, int right, int BOUND1,
                                int MASK, int N, ref long COUNT8                  ) {

  int   bitmap, bit;

  bitmap = MASK & ~ ( left | down | right );

  if ( y == N - 1 )  {
   if ( bitmap != 0 )
    COUNT8++;
  }
  else   {

   if ( y < BOUND1 ) {
    bitmap = bitmap | 2;
    bitmap = bitmap ^ 2;
   }

   while ( bitmap != 0 )   {

    bit    = -bitmap & bitmap;
    bitmap = bitmap ^ bit;

    WorkerBacktrack1 ( y + 1, ( left | bit ) << 1, down | bit, ( right | bit ) >> 1,
                       BOUND1, MASK, N, ref COUNT8                                  );

   }

  }

 }

}