//
//      Distribured NQueens with symmetries, Part II  V. 0.02 - 1-December-2008
//              ( with intervals for 2nd line )
//
using System;

public class Task   {

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

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

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

 }

}

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

public class NQueens   {

 public static long totalCOUNT2 = 0;
 public static long totalCOUNT4 = 0;
 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 (= 2)
  int   M2 = System.Convert.ToInt32 ( args [ 2 ] ); // Number of fixed queens for 2nd backtrack (= 6)
  int   P  = System.Convert.ToInt32 ( args [ 3 ] ); // Number of workers

  int   start = -1;
  int   iterations = Int32.MaxValue;

  if ( args.Length > 4 )  {
   start      = Convert.ToInt32 ( args [ 4 ] ); // for job 1 = 0,1, ... , 22
  }                                             // for jobs 2-12 = 0,1, ... , 20

  if ( args.Length > 5 )  {
   iterations = Convert.ToInt32 ( args [ 5 ] ); // = 1
  }

  NQueens nqueens = new NQueens();

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

  DateTime dt1 = DateTime.Now;

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

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

  DateTime dt2 = DateTime.Now;

  long TOTAL = totalCOUNT2 * 2 + totalCOUNT4 * 4 + totalCOUNT8 * 8;

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

  Console.WriteLine ( "Elapsed time = " + (dt2-dt1).TotalSeconds + " secs." );

 }

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

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

  totalCOUNT2 += COUNT2;
  totalCOUNT4 += COUNT4;
  totalCOUNT8 += COUNT8;

  //Console.WriteLine ( "COUNT4 = " + totalCOUNT4 + " COUNT8 = " + totalCOUNT8.ToString("N") );

  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, int start, int iterations,
                             channel (Task) sendTask                                 ) {

  int   BOUND1;
  int   BOUND2;

  int   bit;

  int[] BOARD = new int [ N ];

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

  int   TOPBIT   = 1 << ( N - 1 );
  int   LASTMASK = TOPBIT | 1;
  int   SIDEMASK = TOPBIT | 1;
  int   ENDBIT   = TOPBIT >> 1;

  int   A = 1;   //   A = 1, 2, ..., 12.

  for ( BOUND1 = 1, BOUND2 = N - 2; BOUND1 <= A; BOUND1++, BOUND2-- )   {

   bit = 1 << BOUND1;
   BOARD [ 0 ] = bit;

   if ( BOUND1 == A )
    MainBacktrack2 ( 1, bit << 1, bit, bit >> 1, BOUND1, BOUND2, BOARD,
                     LASTMASK, SIDEMASK, ENDBIT, MASK, M2, start, iterations, sendTask );

   LASTMASK = LASTMASK | ( LASTMASK >> 1 ) | ( LASTMASK << 1 );
   ENDBIT   = ENDBIT >> 1;

  }

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

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

 }

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

 public void MainBacktrack2 ( int y, int left, int down, int right, int BOUND1, int BOUND2,
                              int[] BOARD, int LASTMASK, int SIDEMASK, int ENDBIT, int MASK,
                              int M2, int start, int iterations, channel (Task) sendTask                              ) {

  int   i;
  int   bitmap, bit;
  int[] newBOARD;

  int   count;

  if ( y == M2 ) {
   newBOARD = new int [ BOARD.Length ];
   for ( i = 0; i < BOARD.Length; i++ )
    newBOARD [ i ] = BOARD [ i ];
   //Console.WriteLine ( "y = " + y + " left = " + left + " down = " + down + " right = " + right );
   sendTask ! ( new Task ( 2, left, down, right, BOUND1, BOUND2, LASTMASK, ENDBIT, newBOARD ) );
  }
  else   {

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

   if ( y < BOUND1 ) {
    bitmap = bitmap | SIDEMASK;
    bitmap = bitmap ^ SIDEMASK;
   }
   else
    if ( y == BOUND2 )   {

     if ( ( down & SIDEMASK ) == 0 )
      return;
     if ( ( down & SIDEMASK ) != SIDEMASK )
      bitmap = bitmap & SIDEMASK;

    }

   if ( y == 1 && start != -1 )   {

    count = 0;
    while ( bitmap != 0 && iterations > 0 )  {

     bit   = -bitmap & bitmap;
     BOARD [ y ] = bit;
     bitmap = bitmap ^ bit;

     if ( count < start )
      count++;
     else {
      MainBacktrack2 ( y + 1, ( left | bit ) << 1, down | bit, ( right | bit ) >> 1,
                       BOUND1, BOUND2, BOARD, LASTMASK, SIDEMASK, ENDBIT, MASK, M2,
                       start, iterations, sendTask                                  );
      iterations--;
     }

    }

   }
   else
    while ( bitmap != 0 )   {

     bit   = -bitmap & bitmap;
     BOARD [ y ] = bit;
     bitmap = bitmap ^ bit;

     MainBacktrack2 ( y + 1, ( left | bit ) << 1, down | bit, ( right | bit ) >> 1,
                     BOUND1, BOUND2, BOARD, LASTMASK, SIDEMASK, ENDBIT, MASK, M2,
                     start, iterations, sendTask                                   );

    }

  }

 }

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

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

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

  long    COUNT2 = 0;
  long    COUNT4 = 0;
  long    COUNT8 = 0;

  int     TOPBIT   = 1 << ( N - 1 );
  int     SIDEMASK = TOPBIT | 1;

  Task   task  = (Task) getTask ? ( COUNT2, COUNT4, COUNT8 );

  while ( task.backtrack != -1 )   {

   if ( task.backtrack == 2 )
    WorkerBacktrack2 ( M2, task.left, task.down, task.right, task.BOUND1, task.BOUND2,
                       task.BOARD, TOPBIT, task.LASTMASK, SIDEMASK, task.ENDBIT, MASK, N,
                       ref COUNT2, ref COUNT4, ref COUNT8                             );

   task   = (Task) getTask ? ( COUNT2, COUNT4, COUNT8 );

   COUNT2 = 0;
   COUNT4 = 0;
   COUNT8 = 0;

  }

  sendStop ! ();

 }

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

 public void WorkerBacktrack2 ( int y, int left, int down, int right, int BOUND1, int BOUND2,
                                int[] BOARD, int TOPBIT, int LASTMASK, int SIDEMASK, int ENDBIT,
                                int MASK, int N, ref long COUNT2, ref long COUNT4, ref long COUNT8 ) {

  int   bitmap, bit;

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

  if ( y == N - 1 )  {
   if ( bitmap != 0 ) {
    if ( ( bitmap & LASTMASK ) == 0 ) {
     BOARD [ y ] = bitmap;
     Check ( BOUND1, BOUND2, BOARD, N, TOPBIT, ENDBIT, ref COUNT2, ref COUNT4, ref COUNT8 );
    }
   }
  }
  else   {

   if ( y < BOUND1 ) {
    bitmap = bitmap | SIDEMASK;
    bitmap = bitmap ^ SIDEMASK;
   }
   else
    if ( y == BOUND2 ) {

     if ( ( down & SIDEMASK ) == 0 )
      return;
     if ( ( down & SIDEMASK ) != SIDEMASK )
      bitmap = bitmap & SIDEMASK;

    }

   while ( bitmap != 0 )   {

    bit    = -bitmap & bitmap;
    BOARD [ y ] = bit;
    bitmap = bitmap ^ bit;

    WorkerBacktrack2 ( y + 1, ( left | bit ) << 1, down | bit, ( right | bit ) >> 1,
                       BOUND1, BOUND2, BOARD, TOPBIT, LASTMASK, SIDEMASK, ENDBIT,
                       MASK, N, ref COUNT2, ref COUNT4, ref COUNT8                  );

   }

  }

 }

 //////////////////////////////////////////////////////////////////////////////////

 public void Check ( int BOUND1, int BOUND2, int[] BOARD, int N, int TOPBIT,
                     int ENDBIT, ref long COUNT2, ref long COUNT4, ref long COUNT8 ) {

  int   own, you, bit, ptn;

  /***   90-degree rotation  ***/

  if ( BOARD [ BOUND2 ] == 1 )   {

   for ( ptn = 2, own = 1; own <= N - 1; own++, ptn = ptn << 1 )   {

    bit = 1;
    for ( you = N - 1; BOARD [ you ] != ptn && BOARD [ own ] >= bit; you-- )
     bit = bit << 1;

    if ( BOARD [ own ] > bit )
     return;
    if ( BOARD [ own ] < bit )
     break;

   }
   if ( own > N - 1 )   {

    COUNT2++;
    return;

   }

  }

  /***   180-degree rotation   ***/

  if ( BOARD [ N - 1 ] == ENDBIT )   {

   for ( you = N - 2, own = 1; own <= N - 1; own++, you-- )   {

    bit = 1;
    for ( ptn = TOPBIT; ptn != BOARD [ you ] && BOARD [ own ] >= bit; ptn = ptn >> 1 )
     bit = bit << 1;

    if ( BOARD [ own ] > bit )
     return;
    if ( BOARD [ own ] < bit )
     break;

   }
   if ( own > N - 1 )   {
    COUNT4++;
    return;
   }

  }

  /***   270-degree rotation   ***/

  if ( BOARD [ BOUND1 ] == TOPBIT )    {

   for ( ptn = TOPBIT >> 1, own = 1; own <= N - 1; own++, ptn = ptn >> 1 ) {

    bit = 1;
    for ( you = 0; BOARD [ you ] != ptn && BOARD [ own ] >= bit; you++ )
     bit = bit << 1;

    if ( BOARD [ own ] > bit )
     return;
    if ( BOARD [ own ] < bit )
     break;

   }

  }
  COUNT8++;

 }

}