//
//    NQueens with symmetries  V. 0.02 - 17-09-2008
//
using System;

public class SYMM_NQueens {

 public static void Main ( String[] args )   {

  int   bit;
  int   BOUND1, BOUND2;

  DateTime dt1 = DateTime.Now;

  int   N = Convert.ToInt32 ( args [ 0 ] );

  int[] BOARD  = new int [ N ];

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

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

  BOARD [ 0 ] = 1;

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

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

   Backtrack1 ( 2, ( 2 | bit ) << 1, 1 | bit, bit >> 1, BOUND1, BOARD, N, MASK, ref COUNT8 );

  }

  Console.WriteLine ( "AFTER BT1: COUNT8 = " + COUNT8 );

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

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

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

   Backtrack2 ( 1, bit << 1, bit, bit >> 1, BOUND1, BOUND2, BOARD,
                TOPBIT, LASTMASK, SIDEMASK, ENDBIT, N, MASK,
                ref COUNT2, ref COUNT4, ref COUNT8                 );

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

  }

  Console.WriteLine ( "AFTER BT1: COUNT2 = " + COUNT2 + " COUNT4 = " + COUNT4 + " COUNT8 = " + COUNT8 );

  DateTime  dt2 = DateTime.Now;

  long UNIQUE = COUNT8 + COUNT4 + COUNT2;
  long TOTAL  = COUNT8 * 8 + COUNT4 * 4 + COUNT2 * 2;

  Console.WriteLine ( "COUNT2 = " + COUNT2 + "  COUNT4 = " + COUNT4 + "  COUNT8=" + COUNT8 );
  Console.WriteLine ( "UNIQUE = " + UNIQUE + "   " + "TOTAL = " + TOTAL );

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

 }

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

 public static void Backtrack1 ( int y, int left, int down, int right, int BOUND1,
                                 int[] BOARD, int N, int MASK, ref int COUNT8 )     {


  int   bitmap, bit;

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

  if ( y == N - 1 )   {
   if ( bitmap != 0 ) {
    BOARD [ y ] = bitmap;
    COUNT8++;
    //Display ( BOARD, N );
   }
  }
  else   {
   if ( y < BOUND1 ) {
    bitmap = bitmap | 2;
    bitmap = bitmap ^ 2;
   }
   while ( bitmap != 0 )   {
    bit    = -bitmap & bitmap;
    bitmap = bitmap ^ bit;
    BOARD [ y ] = bit;
    Backtrack1 ( y + 1, ( left | bit ) << 1, down | bit, ( right | bit ) >> 1,
                 BOUND1, BOARD, N, MASK, ref COUNT8                            );
   }

  }

 }

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

 public static void Backtrack2 ( int y, int left, int down, int right,
                                 int BOUND1, int BOUND2, int[] BOARD,
                                 int TOPBIT, int LASTMASK, int SIDEMASK, int ENDBIT,
                                 int N, int MASK, ref int COUNT2, ref int COUNT4,
                                 ref int 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;

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

   }

  }

 }

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

 public static void Check ( int BOUND1, int BOUND2, int[] BOARD, int N,
                            int TOPBIT, int ENDBIT,
                            ref int COUNT2, ref int COUNT4, ref int 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++;
    // Display ( BOARD, N );
    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++;
    // Display ( BOARD, N );
    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++;

  // Display ( BOARD, N );

 }

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

 public static void Display ( int[] BOARD, int N )    {

  int   y, bit;

  Console.WriteLine();

  for ( y = 0; y < N; y++ )   {

   for ( bit = 1 << ( N - 1 ); bit != 0; bit = bit >> 1 )
    Console.Write ( ( ( BOARD [ y ] & bit ) != 0 ) ? "Q" : "-" );
   Console.WriteLine();

  }

 }

}