The Optimal Queens

by Timothy Rolfe





Listing One



void Nqueens (int Board[], int Trial[], int Size, int Row)

{

   if (Row == Size)

      Process(Board, Size);

   else

      for (int Col = 0; Col < Size; Col++)

      {

         Board[Row] = Col;

         if ( Valid (Board, Size, Row) )

            Nqueens (Board, Trial, Size, Row+1);

      }

}





Listing Two



int Valid (int Board[], int Size, int Row)

{

   for (int Idx = 0; Idx < Row; Idx++)

      if (  Board[Idx] == Board[Row] ||

            abs(Board[Row]-Board[Idx]) == (Row-Idx) )

         return 0;    // boolean false

   return 1;          // boolean true

}

Listing Three

int Valid (int Board[], int Size, int Row,

           int Col[], int Diag[], int AntiD[] )

{

   int Idx;        /* Index into Diag[] / AntiD[] */

   int Chk;        /* Occupied flag               */



   Chk = Col[Board[Row]];

/* Diagonal:  Row-Col == constant */

   Idx = Row - Board[Row] + Size-1;

   Chk = Chk || Diag[Idx];

/* AntiDiagonal:  Row+Col == constant */

   Idx = Row + Board[Row];

   Chk = Chk || AntiD[Idx];

   return !Chk;    /* Valid if NOT any occupied  */

}





Listing Four



void Nqueens (int Board[],int Size, int Row)

{

   int Idx, Lim, Vtemp;



/* Check for a partial board. */

   if (Row < Size-1)

   {

      if (Valid (Board, Size, Row)

         Nqueens (Board, Trial, Size, Row+1);

      for (Idx = Row+1; Idx < Size; Idx++)

      {

         Vtemp = Board[Idx];

         Board[Idx] = Board[Row];

         Board[Row] = Vtemp;

         if (Valid (Board, Size, Row))

            Nqueens (Board, Trial, Size, Row+1);

         }

      }

/*    Regenerate original vector from Row to Size-1:  */

      Vtemp = Board[Row];

      for (Idx = Row+1; Idx < Size; Idx++)

         Board[Idx-1] = Board[Idx];

      Board[Idx-1] = Vtemp;

   }

/* This is a complete board.  Final validity check    */

   else if ( Valid (Board, Size, Row) )

      Process(Board, Size);

}





Listing Five



/* Check the symmetries.  Return 0 if this is not the 1st     */

/* solution in the set of equivalent solutions; otherwise     */

/* return the number of equivalent solutions.                 */

int SymmetryOps(

    int Board[],     /* The fully-populated board             */

    int Trial[],     /* Used for symmetry checks              */

                     /* Holds its own scratch space too!      */

    int Size)        /* Number of cells in a row/column       */

{  int  Idx;         /* Loop variable; intncmp result         */

   int  Nequiv;      /* Number equivalent boards              */

   int *Scratch=&Trial[Size];   /* Scratch space              */



/* Copy; Trial will be subjected to the transformations       */

   for (Idx = 0; Idx < Size; Idx++)

      Trial[Idx] = Board[Idx];



/* 90 degrees --- clockwise (4th parameter of Rotate is FALSE)*/

   Rotate (Trial, Scratch, Size, false);

   Idx = intncmp (Board, Trial, Size);

   if (Idx > 0) return 0;

   if ( Idx == 0 )  /* No change on 90 degree rotation        */

      Nequiv = 1;

   else                                       /*  180 degrees */

   {  Rotate (Trial, Scratch, Size, false);

      Idx = intncmp (Board, Trial, Size);

      if (Idx > 0) return 0;

      if ( Idx == 0 ) /* No change on 180 degree rotation     */

         Nequiv = 2;

      else                                    /* 270 degrees  */

      {  Rotate (Trial, Scratch, Size, false);

         Idx = intncmp (Board, Trial, Size);

         if (Idx > 0) return 0;

         Nequiv = 4;

      }

   }

/* Copy the board into Trial for rotational checks */

   for (Idx = 0; Idx < Size; Idx++)

      Trial[Idx] = Board[Idx];

/* Reflect -- vertical mirror */

   Vmirror (Trial, Size);

   Idx = intncmp (Board, Trial, Size);

   if (Idx > 0) return 0;

   if ( Nequiv > 1 )    // I.e., no four-fold rotational symmetry

   {

/* -90 degrees --- equiv. to diagonal mirror */

      Rotate (Trial, Scratch, Size, true);

      Idx = intncmp (Board, Trial, Size);

      if (Idx > 0) return 0;

      if ( Nequiv > 2 ) // I.e., no two-fold rotational symmetry

      {

/* -180 degrees --- equiv. to horizontal mirror */

         Rotate (Trial, Scratch, Size, true);

         Idx = intncmp (Board, Trial, Size);

         if (Idx > 0) return 0;

/* -270 degrees --- equiv. to anti-diagonal mirror */

         Rotate (Trial, Scratch, Size, true);

         Idx = intncmp (Board, Trial, Size);

         if (Idx > 0) return 0;

      }

   }

/* WE HAVE A GOOD ONE! */

   return Nequiv * 2;  /* Double to handle the mirror images */

}





Listing Six



public class Board

{  private int nSoln = 0,    // Total solutions for this board

               nUniq = 0;    // Unique solutions, rejecting ones

                             // equivalent based on rotations.

   private int size,         // Board size AND number of queens

               limit,        // First row mid-point

               nextCol = 0;  // Next position to be computed



   public Board (int size)

   {  this.size = size;

      limit = (size+1) / 2;  // Mirror images done automatically

   }



// Accumulate partial results and assign the next problem.

// Synchronized because this is the critical section ---

// only one thread allowed in at a time.

   public synchronized int nextJob ( int nS, int nU)

   {  nSoln += nS;

      nUniq += nU;

   // If all columns have been assigned, return the exit flag

      return nextCol < limit ? nextCol++ : -1;

   }

}

// Return the saved information on total solutions

   public int total(){  return nSoln;  }



// Return the saved information on unique solutions

   public int unique(){  return nUniq;  }

}





Listing Seven



public WorkEngine(int size, int nMore, Board info)

{  this.size = size;

   this.info = info;

   board     = new int[size];

   trial     = new int[size];

   scratch   = new int[size];

   diagChk   = new boolean[2*size-1];

   antiChk   = new boolean[2*size-1];

   if ( nMore > 0 )

      try

      {  child = new WorkEngine( size, nMore-1, info );

         child.start();

      }

      catch ( Exception e )

      {  System.out.println(e);  }

   else

      child = null;

}





Listing Eight



public void run()

{  int  nextCol;

   long start = System.currentTimeMillis();



   while ( true )    // Will break out on -1 for column posn.

   {  int row, col;



   // On the first call, nTotal and nUnique hold zeroes.

      nextCol = info.nextJob(nTotal, nUnique);

      if ( nextCol < 0 )

         break;

   // Empty out counts from the last board processed

      nTotal = nUnique = 0;

   // Generate the initial permutation vector, given nextCol

      board[0] = nextCol;

      for ( row = 1, col = 0; row < size; row++, col++ )

         board[row] = col == nextCol ? ++col : col;

   // Empty out the diagChk and antiChk vectors

      for ( row = 0; row < 2*size-1; row++ )

         diagChk[row] = antiChk[row] = false;

   // Mark as inuse the diagonal and antidiagonal

      diagChk[size-1-nextCol] = antiChk[nextCol] = true;

   // Now compute from row 1 on down.

      nQueens (1);

   }

   if ( child != null )

      try

      {  child.join();  }

      catch ( Exception e )

      {  System.out.println(e);  }

}







