modified Queens.c –

/*
    Derived from Queens.c from the article "Optimal Queens - A classical problem
    solved by backtracking" by Timothy Rolfe [Eastern Washington University]
    in Dr Dobb's Journal  May 2005.

    Adapted for Macintosh CodeWarrior 8.3 carbon console under OS-X 10.3.9
    by F.C. Kuechmann, 1-3 May 2005.  Memory variables *Col, *Diag, *AntiD
    made global in order to allow continuous operation for all queens numbers
    4-18 and all optimizations 0-3.
*/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <ctype.h>
#include <string.h>
#include <DateTimeUtils.h>


#define kSecsInHr 3600
#define kSecsInMin 60
#define kMaxQueens 18
#define kMinQueens 4

long int Nunique, Ntotal;
short  Opt1, Opt2;
short int *Col, *Diag, *AntiD;



        /* Check two vectors for equality; return first inequality
         (a la strncmp) */
int intncmp (int L[], int R[], int N)
{
   int Idx;

   for (Idx = 0; Idx < N; Idx++)
   {
      if ( L[Idx] - R[Idx] )
      {
         return L[Idx]-R[Idx];
      }    /*if*/
   }    /*for*/
   return 0;
}

            /* Rotate +90 or -90: */
void Rotate(int R[], int C[], int N, int Neg)
{
   int Idx, Jdx;

   Jdx = Neg ? 0 : N-1;
   for (Idx = 0; Idx < N; Neg ? Jdx++ : Jdx--)
   {
      C[Idx++] = R[Jdx];
   }    /*for*/

   Jdx = Neg ? N-1 : 0;
   for (Idx = 0; Idx < N; Neg ? Jdx-- : Jdx++)
   {
      R[C[Idx++]] = Jdx;
   }    /*for*/
}

void Vmirror(int R[], int N)
{
   int Idx;

   for (Idx = 0; Idx < N; Idx++)
   {
      R[Idx] = (N-1) - R[Idx];
   }    /*for*/

   return;
}

int SymmetryOps(
    int Board[],               /* The fully-populated board         */
    int Trial[],               /* Used for symmetry checks          */
                               /* Holds its own scratch space too!  */
    int Nqueenz)                  /* Number of cells in a row/column   */
{
   int     Idx;                /* Loop variable, array difference   */
   int     Nequiv;             /* Number equivalent boards          */

                                /* Copy over; now Trial will be subjected to the transformations    */
   for (Idx = 0; Idx < Nqueenz; Idx++)
   {
      Trial[Idx] = Board[Idx];
   }    /*for*/

                                /* 90 degrees --- clockwise */
   Rotate (Trial, &Trial[Nqueenz], Nqueenz, 0);
   Idx = intncmp (Board, Trial, Nqueenz);
   if (Idx > 0)
   {
           return 0;
   }    /*if*/

   if (Idx == 0)
   {
      Nequiv = 1;
   }
   else
   {
                        /* 180 degrees */
      Rotate (Trial, &Trial[Nqueenz], Nqueenz, 0);
      Idx = intncmp (Board, Trial, Nqueenz);
      if (Idx > 0)
      {
          return 0;
      }    /*if*/

      if (Idx == 0)
      {
         Nequiv = 2;
      }
      else
      {
                    /* 270 degrees */
         Rotate (Trial, &Trial[Nqueenz], Nqueenz, 0);
         Idx = intncmp (Board, Trial, Nqueenz);
         if (Idx > 0)
         {
                return 0;
         }        /*if*/
         Nequiv = 4;
      }    /*if*/
   }    /*if*/
                /* Reflect -- vertical mirror */
   for (Idx = 0; Idx < Nqueenz; Idx++)
   {
      Trial[Idx] = Board[Idx];
   }    /*for*/

   Vmirror (Trial, Nqueenz);
   Idx = intncmp (Board, Trial, Nqueenz);
   if (Idx > 0)
   {
           return 0;
   }    /*if*/
                /* -90 degrees --- equiv. to diagonal mirror */
   Rotate (Trial, &Trial[Nqueenz], Nqueenz, -1);
   Idx = intncmp (Board, Trial, Nqueenz);
   if (Idx > 0)
   {
           return 0;
   }    /*if*/

   if (Idx < 0)
   {
                    /*   -180 degrees --- equiv. to horizontal mirror */
     Rotate (Trial, &Trial[Nqueenz], Nqueenz, -1);
     Idx = intncmp (Board, Trial, Nqueenz);
     if (Idx > 0)
     {
             return 0;
     }        /*if*/

     if (Idx < 0)
     {
                        /*       -270 degrees --- equiv. to anti-diagonal mirror */
         Rotate (Trial, &Trial[Nqueenz], Nqueenz, -1);
         Idx = intncmp (Board, Trial, Nqueenz);
         if (Idx > 0)
         {
                 return 0;
         }        /*if*/
     }        /*if*/
   }    /*if*/
                    /* WE HAVE A GOOD ONE! */
   return Nequiv * 2;
}

void Mark (int R, int C, int Nqueenz, short Flag)
{
   int Idx;

   Col[C] = Flag;
                    /* Diagonal:  Row-Col == constant */
   Idx = R - C + Nqueenz-1;
   Diag[Idx] = Flag;
                /* AntiDiagonal:  Row+Col == constant */
   Idx = R + C;
   AntiD[Idx] = Flag;
}

int Valid (int Board[], int Nqueenz, int Row)
{
   int   Idx;      /* Index into Diag[] / AntiD[] */
   short Chk;      /* Occupied flag               */
   int p;

   if (Opt1)
   {
      Chk = Col[Board[Row]];
                       /* Diagonal:  Row-Col == constant */
      Idx = Row - Board[Row] + Nqueenz-1;
      Chk = Chk || Diag[Idx];
                   /* AntiDiagonal:  Row+Col == constant */
      Idx = Row + Board[Row];
      Chk = Chk || AntiD[Idx];
      return !Chk; /* Valid if NOT any occupied   */
   }
   else
   {
      for (Idx = 0; Idx < Row; Idx++)
      {
         p =  abs(Board[Row]-Board[Idx]);
         if (  Board[Idx] == Board[Row] || p == (Row-Idx) )
         {
            return 0;
         }    /*if*/
      }    /*for*/
      return 1;
   }    /*if*/
}

void Nqueens (int Board[], int Trial[], int Nqueenz, int Row)
{
   int Idx, Lim, Vtemp;

   if (Row < Nqueenz-1)
   {
      if (Valid (Board, Nqueenz, Row))
      {
         if (Opt1)
         {
            Mark (Row, Board[Row], Nqueenz, 1);
         }    /*if*/

         Nqueens (Board, Trial, Nqueenz, Row+1);
         if (Opt1)
         {
            Mark (Row, Board[Row], Nqueenz, 0);
         }    /*if*/
      }    /*if*/

      Lim = Row ? Nqueenz : (Nqueenz+1)/2 ;
      for (Idx = Row+1; Idx < Lim; Idx++)
      {
         Vtemp = Board[Idx];
         Board[Idx] = Board[Row];
         Board[Row] = Vtemp;
         if (Valid (Board, Nqueenz, Row))
         {
            Mark (Row, Board[Row], Nqueenz, 1);
            Nqueens (Board, Trial, Nqueenz, Row+1);
            Mark (Row, Board[Row], Nqueenz, 0);
         }    /*if*/
      }    /*for*/
                                /* Regenerate original vector from Row to Nqueenz-1:  */
      Vtemp = Board[Row];
      for (Idx = Row+1; Idx < Nqueenz; Idx++)
      {
         Board[Idx-1] = Board[Idx];
      }    /*for*/

      Board[Idx-1] = Vtemp;
   }
   else
   {
      if ( !Valid (Board, Nqueenz, Row) )
      {
         return;
      }    /*if*/

      Idx = SymmetryOps (Board, Trial, Nqueenz);
      if (Idx)
      {
         Nunique++;
         Ntotal += Idx;
      }    /*if*/
   }    /*if*/

   return;
}

void Nqueens1 (int Board[], int Trial[], int Nqueenz, int Row)
{
   int Colum;
   int Tst;


   if (Row == Nqueenz)
   {
      Tst = SymmetryOps (Board, Trial, Nqueenz);
      if (Tst)
      {
         Nunique++;
         Ntotal += Tst;
      }    /*if*/
   }
   else
   {
      for (Colum = 0; Colum < Nqueenz; Colum++)
      {
         Board[Row] = Colum;
         if (Valid (Board, Nqueenz, Row))
         {
            if (Opt1)
            {
               Mark (Row, Board[Row], Nqueenz, 1);
            }    /*if*/

            Nqueens1 (Board, Trial, Nqueenz, Row+1);
            if (Opt1)
            {
               Mark (Row, Board[Row], Nqueenz, 0);
            }    /*if*/
         }    /*if*/
      }    /*for*/
   }    /*if*/
}

void DoIt(int Idx, int Nqueenz)
{
   int  *Board, *Trial;

   Opt1 = Idx & 1;
   Opt2 = (Idx>>1) & 1;

    printf ("Opt1 = %2d\n", Opt1);
    printf ("Opt2 = %2d\n", Opt2);

   Board = (int *) calloc (Nqueenz, sizeof *Board);
   Trial = (int *) calloc (Nqueenz*2, sizeof *Board);
                /* Initial permutation generated. */
   for (Idx = 0; Idx < Nqueenz; Idx++)
   {
      Board[Idx] = Idx;
   }/*for*/
        AntiD = NULL;
   Col = (short *) calloc (Nqueenz, sizeof *Col);
   Diag = (short *) calloc ( 2*Nqueenz-1, sizeof *Diag );
   AntiD = (short *) calloc ( 2*Nqueenz-1, sizeof *AntiD );
   if ( !AntiD )
   {
        printf ("calloc failed --- out of memory!");
        exit (6);
   }    /*if*/
           if (Opt2)
   {
      Nqueens (Board, Trial, Nqueenz, 0);
   }
   else
   {
      Nqueens1(Board, Trial, Nqueenz, 0);           }    /*if*/

   free(Col);
   free(Diag);
   free(AntiD);
   free(Board);
   free(Trial);
}


void     PrintLapsed(unsigned long Lapsed)
{
    int quot;
        quot = Lapsed/kSecsInHr;
    printf (" %02d", quot);
    Lapsed = Lapsed - (quot * kSecsInHr);
    quot = Lapsed/kSecsInMin;
    printf (" : %02d", quot);
    Lapsed = Lapsed - (quot * kSecsInMin);
    printf (" : %02d\n\n", Lapsed);
}


void PrintDateTime(DateTimeRec theTime)
{
    printf ("%02d", theTime.day);
        switch (theTime.month)
    {
        case 1:
            printf (" Jan  ");
            break;
        case 2:
            printf (" Feb ");
            break;
        case 3:
            printf (" Mar ");
            break;
        case 4:
            printf (" Apr ");
            break;
        case 5:
            printf (" May ");
            break;
        case 6:
            printf (" Jun ");
            break;
        case 7:
            printf (" Jul ");
            break;
        case 8:
            printf (" Aug ");
            break;
        case 9:
            printf (" Sep ");
            break;
        case 10:
            printf (" Oct ");
            break;
        case 11:
            printf (" Nov ");
            break;
        case 12:
            printf (" Dec ");
            break;        }    /*switch*/

    printf ("%04d", theTime.year);
    printf ("  %02d", theTime.hour);
    printf (" : %02d", theTime.minute);
    printf (" : %02d\n", theTime.second);
}



int main(void)
{
    int Idx, Nqueenz, min, max, p;
    unsigned long begsecs, finsecs, bgsecs, fnsecs,
            opt0secs, opt1secs, opt2secs, opt3secs, Lapsed;
    DateTimeRec begTime, finTime;

    Nqueenz = 0;
    p = 0;
    Idx = 0;
    opt0secs = 0;
    opt1secs = 0;
    opt2secs = 0;
    opt3secs = 0;
    min = kMinQueens;
    max = kMaxQueens + 1;
    printf ("N-Queens");
    printf ("\n\n\n");
    GetDateTime(&begsecs);
    GetTime(&finTime);    /*do this just to init*/
    GetDateTime(&finsecs); /* init */
    GetTime(&begTime);
        for(Nqueenz=min; Nqueenz<max; Nqueenz++)
    {
        printf ("\n\n");                for(Idx=0; Idx<4; Idx++)
        {
            Nunique = 0;
            Ntotal  = 0;
            GetTime(&finTime); PrintDateTime(finTime);

            printf ("N-Queens = %2d\n", Nqueenz);
            printf ("Optimization:  %1d\n", Idx);
            GetDateTime(&bgsecs);
            DoIt(Idx, Nqueenz);
            GetDateTime(&fnsecs);
            Lapsed = fnsecs - bgsecs;
            printf ("Solutions:  %10ld\n", Ntotal);
            printf ("Unique:     %10ld\n", Nunique);
            printf ("Time [sec]: %10ld\n", Lapsed);
            switch (Idx)
            {
                case 0:
                    opt0secs += Lapsed;
                    break;
                case 1:
                    opt1secs += Lapsed;
                    break;
                case 2:
                    opt2secs += Lapsed;
                    break;
                case 3:
                    opt3secs += Lapsed;
                    break;
            }    /*switch*/
                        printf ("Time :    ");
            PrintLapsed(Lapsed);
        }    /*for*/
    }        /*for*/
    GetDateTime(&finsecs);
    Lapsed = finsecs - begsecs;
        printf ("\n\nTime [sec]:      %10ld\n", Lapsed);
        printf ("Total Time :   ");
    PrintLapsed(Lapsed);
        for(p=0; p<4; p++)
    {
         switch (p)
          {
                 case 0:
                    Lapsed = opt0secs;
                    printf ("\nOptimization 0 Time [sec]: %10ld\n", Lapsed);
                    break;
                case 1:
                    Lapsed = opt1secs;
                    printf ("\nOptimization 1 Time [sec]: %10ld\n", Lapsed);
                    break;
                case 2:
                    Lapsed = opt2secs;
                    printf ("\nOptimization 2 Time [sec]: %10ld\n", Lapsed);
                    break;
                case 3:
                    Lapsed = opt3secs;
                    printf ("\nOptimization 3 Time [sec]: %10ld\n", Lapsed);
                    break;
         }    /*switch*/
                 PrintLapsed(Lapsed);
    } /*for*/
        GetTime(&finTime);             printf ("\n\nStarted  : ");
    PrintDateTime(begTime);

    printf ("Finished : ");
    PrintDateTime(finTime);
        printf ("\n\nWhere ignorance is bliss, 'tis folly to be wise.\n");
    return 0;
}    /* That's all, folks! */

---------------------------------------------

Saved console output for a run –

N-Queens

23 May 2005  22 : 14 : 26
N-Queens =  4
Optimization:  0
Opt1 =  0
Opt2 =  0
Solutions:           2
Unique:              1
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  4
Optimization:  1
Opt1 =  1
Opt2 =  0
Solutions:           2
Unique:              1
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  4
Optimization:  2
Opt1 =  0
Opt2 =  1
Solutions:           2
Unique:              1
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  4
Optimization:  3
Opt1 =  1
Opt2 =  1
Solutions:           2
Unique:              1
Time [sec]:          0
Time :     00 : 00 : 00



23 May 2005  22 : 14 : 27
N-Queens =  5
Optimization:  0
Opt1 =  0
Opt2 =  0
Solutions:          10
Unique:              2
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  5
Optimization:  1
Opt1 =  1
Opt2 =  0
Solutions:          10
Unique:              2
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  5
Optimization:  2
Opt1 =  0
Opt2 =  1
Solutions:          10
Unique:              2
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  5
Optimization:  3
Opt1 =  1
Opt2 =  1
Solutions:          10
Unique:              2
Time [sec]:          0
Time :     00 : 00 : 00



23 May 2005  22 : 14 : 27
N-Queens =  6
Optimization:  0
Opt1 =  0
Opt2 =  0
Solutions:           4
Unique:              1
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  6
Optimization:  1
Opt1 =  1
Opt2 =  0
Solutions:           4
Unique:              1
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  6
Optimization:  2
Opt1 =  0
Opt2 =  1
Solutions:           4
Unique:              1
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  6
Optimization:  3
Opt1 =  1
Opt2 =  1
Solutions:           4
Unique:              1
Time [sec]:          0
Time :     00 : 00 : 00



23 May 2005  22 : 14 : 27
N-Queens =  7
Optimization:  0
Opt1 =  0
Opt2 =  0
Solutions:          40
Unique:              6
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  7
Optimization:  1
Opt1 =  1
Opt2 =  0
Solutions:          40
Unique:              6
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  7
Optimization:  2
Opt1 =  0
Opt2 =  1
Solutions:          40
Unique:              6
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  7
Optimization:  3
Opt1 =  1
Opt2 =  1
Solutions:          40
Unique:              6
Time [sec]:          0
Time :     00 : 00 : 00



23 May 2005  22 : 14 : 27
N-Queens =  8
Optimization:  0
Opt1 =  0
Opt2 =  0
Solutions:          92
Unique:             12
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  8
Optimization:  1
Opt1 =  1
Opt2 =  0
Solutions:          92
Unique:             12
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  8
Optimization:  2
Opt1 =  0
Opt2 =  1
Solutions:          92
Unique:             12
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  8
Optimization:  3
Opt1 =  1
Opt2 =  1
Solutions:          92
Unique:             12
Time [sec]:          0
Time :     00 : 00 : 00



23 May 2005  22 : 14 : 27
N-Queens =  9
Optimization:  0
Opt1 =  0
Opt2 =  0
Solutions:         352
Unique:             46
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  9
Optimization:  1
Opt1 =  1
Opt2 =  0
Solutions:         352
Unique:             46
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  9
Optimization:  2
Opt1 =  0
Opt2 =  1
Solutions:         352
Unique:             46
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens =  9
Optimization:  3
Opt1 =  1
Opt2 =  1
Solutions:         352
Unique:             46
Time [sec]:          0
Time :     00 : 00 : 00



23 May 2005  22 : 14 : 27
N-Queens = 10
Optimization:  0
Opt1 =  0
Opt2 =  0
Solutions:         724
Unique:             92
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens = 10
Optimization:  1
Opt1 =  1
Opt2 =  0
Solutions:         724
Unique:             92
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens = 10
Optimization:  2
Opt1 =  0
Opt2 =  1
Solutions:         724
Unique:             92
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens = 10
Optimization:  3
Opt1 =  1
Opt2 =  1
Solutions:         724
Unique:             92
Time [sec]:          0
Time :     00 : 00 : 00



23 May 2005  22 : 14 : 27
N-Queens = 11
Optimization:  0
Opt1 =  0
Opt2 =  0
Solutions:        2680
Unique:            341
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens = 11
Optimization:  1
Opt1 =  1
Opt2 =  0
Solutions:        2680
Unique:            341
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens = 11
Optimization:  2
Opt1 =  0
Opt2 =  1
Solutions:        2680
Unique:            341
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 27
N-Queens = 11
Optimization:  3
Opt1 =  1
Opt2 =  1
Solutions:        2680
Unique:            341
Time [sec]:          0
Time :     00 : 00 : 00



23 May 2005  22 : 14 : 27
N-Queens = 12
Optimization:  0
Opt1 =  0
Opt2 =  0
Solutions:       14200
Unique:           1787
Time [sec]:          1
Time :     00 : 00 : 01

23 May 2005  22 : 14 : 28
N-Queens = 12
Optimization:  1
Opt1 =  1
Opt2 =  0
Solutions:       14200
Unique:           1787
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 28
N-Queens = 12
Optimization:  2
Opt1 =  0
Opt2 =  1
Solutions:       14200
Unique:           1787
Time [sec]:          0
Time :     00 : 00 : 00

23 May 2005  22 : 14 : 28
N-Queens = 12
Optimization:  3
Opt1 =  1
Opt2 =  1
Solutions:       14200
Unique:           1787
Time [sec]:          0
Time :     00 : 00 : 00



23 May 2005  22 : 14 : 28
N-Queens = 13
Optimization:  0
Opt1 =  0
Opt2 =  0
Solutions:       73712
Unique:           9233
Time [sec]:          4
Time :     00 : 00 : 04

23 May 2005  22 : 14 : 32
N-Queens = 13
Optimization:  1
Opt1 =  1
Opt2 =  0
Solutions:       73712
Unique:           9233
Time [sec]:          1
Time :     00 : 00 : 01

23 May 2005  22 : 14 : 33

