Backtracking Algorithms
by Timothy Rolfe


Listing One

// Set remaining values into position size and recurse (if needed)
void Cloque::build ( IntQueue &work, int posn )
{   if ( work.isEmpty() )  // Face has been completed
   {  if ( face[posn-1] < face[1] )  // Omit the mirror image
         process();       // Process as a valid clock face.
   }
   else
   {  int marker = work.nextItem();
      do
      {  face[posn] = work.dequeue();
         if (check(posn))
            build(work, posn+1);
         work.enqueue(face[posn]);
      }  while ( marker != work.nextItem() );
   } // end if ( work.isEmpty() ) / else
} // end build()


Listing Two

// Check whether the current clock face meets the restriction on
// the maximum allowed triplet sum.  Note that this presumes that
// the face is valid UP TO making an entry into this position.
bool Cloque::check ( int posn )  // I.e., position being filled
{  int idx,
       total = 0;
   numCheckCalls ++;
   idx = posn - 2;
   if ( idx < 0 )
      idx = 0;
   while ( idx <= posn )
      total += face[idx++];
   if ( total > maxTot )
      return false;
// At the end, test the wrap-around cases:
   if ( posn == size-1 )
   {
      total = face[posn-1] + face[posn] + face[0];
      if ( total > maxTot )
         return false;
      total = face[posn] + face[0] + face[1];
      if ( total > maxTot )
         return false;
   } // end if ( posn...
   return true;
} // end check()


Listing Three

void  Permute ( int X[], int Lim, int N, int MaxSum )
{  int j;     // Loop variable
// First possibility:  start-up case moving values through [0]
   if ( Lim == 0 )
   {
      Permute (X, 2, N, MaxSum);
      for ( j = 2; j < N; j++ )
      {
         Swap ( j, 0, X );
      // Note that X[1] is left unchanged at N-1.
         Permute (X, 2, N, MaxSum);
      }
   // We will not bother regenerating the array here.
   }
// Next possibility:  intermediate case (incomplete permutation)
   else if ( Lim < N-1 )
   {  int hold;
      int PairSum = X[Lim-2] + X[Lim-1];
   // Check the initial state
      if ( X[Lim]+PairSum <= MaxSum )
         Permute (X, Lim+1, N, MaxSum);

      for ( j = Lim+1; j < N; j++ )
      {
         Swap ( j, Lim, X );
      // Omit work if it gives an invalid result
         if ( X[Lim]+PairSum > MaxSum )
            continue;
      // Check for mirror-image rejection
      // Note that X[1] contains the value N-1.
         if ( Lim == 2 && X[0] > X[Lim] )
            continue;
         Permute (X, Lim+1, N, MaxSum);
      }
   // Regenerate the array state.
      hold = X[Lim];

      for ( j = Lim+1; j < N; j++ )
         X[j-1] = X[j];
      X[N-1] = hold;
   }
// Final possibility:  complete permutation, so check for validity
   else if ( Check(X, Lim, N, MaxSum) )
         Process (X, N);
// else it fails at the very end!
}



1


