The La
          Plata Mountains as seen from above the authorís home.



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

//
//                                    HIQ.C
//
//  This program counts the number of solutions to the "Hi-Q" peg game.
//  (33 hole peg solitaire.)
//
//  The algorithm tries all possible move combinations and saves the resulting
//  board position after each move. These positions can then be subsequently
//  recognized (including rotations and reflections where applicable) and their
//  results used without repeating the search sequence.
//
//  Positions on the peg board are defined as follows:
//
//            0  1  2              Initially pegs
//            3  4  5              exist in all holes
//      6  7  8  9 10 11 12        except the user's choice for the
//     13 14 15 16 17 18 19        start hole which is empty.
//     20 21 22 23 24 25 26
//           27 28 29
//           30 31 32
//
//  The number "MAX_HIST" defines the amount of array space (and RAM) that
//  the program uses.
//
//  The program will compile and run as is if you use the lcc win32 C compiler.
//  As it currently configured, the program requires 2 GB of free RAM, but you
//  can run it using less RAM if you decrease the size of MAX_HIST. (This may
//  also slow down the solution speed for some combinations.)
//
//  When the program runs it will ask you a couple of questions before it
//  begins the search. (See the InitSys() routine.) The program will display
//  interim stack results while it is running.
//
//  Running time to find all solutions for the standard game is about 7 min.
//  Running time to find and output a solution is usually less than one second.
//
//*****************************************************************************

#include <stdheaders.h>          //  The usual <stdio.h> etc

#define MAX_HIST 470000000       //  Upper limit to nbr of elements in the
#define MAX_HIST10 MAX_HIST+10   //  history array. If your computer only has
                                 //  2 GB of RAM, a good value for MAX_HIST
                                 //  would be 300,000,000 (but without commas)
                                 //  If you have more that 2 GB RAM, set
                                 //  MAX_HIST to 470,000,000.

                                 //  Define functions
void InitSys(void);              //  User input and initialization
void GetScore(void);             //  Converts board positions to a "score"
unsigned CkHist(void);           //  Checks to see if current board seen before
void GetSol(unsigned);           //  Get nbr of sol. from Hist[unsigned].
void Stk2Hist(int);              //  Creates a history record for current stack data
void PauseMsg(void);             //  Pauses the program for user viewing
void PosCount(void);             //  Outputs number of positions seen.
void Bin2Dec(int);               //  Converts the binary number at Stack[int]
                                 //  to a decimal number

int StkMove[36];                 //  Move sequences are stored in a stack
unsigned StkLowBin[36];          //  Nbr of Sol - lowest 23 binary digits
unsigned StkMidBin[36];          //  Nbr of Sol - middle 31 binary digits
unsigned StkHighBin[36];         //  Nbr. of Sol - highest 31 binary digits.
unsigned Stk24low[36];           //  The 24 low (index) bits for the score.
unsigned Stk9high[36];           //  The remaining 9 high bits in the score.
                                 //  "Score" is the bit representation of the
                                 //  current 33 hole board position.


    //  A record is entered into the history array each time the search of a
    //  subtree from a stack position is complete. Each record keeps the
    //  high 9 bits of the score pattern (Stk9high[]), the number of solutions
    //  found for this pattern, and a link to the next record that shares the
    //  same index link list (Ptrn24low). These 24 low bits are used to index
    //  into the HistHead[] array.

    //  The records themselves are variable length with data stored as follows:

    //  The first array element in a record (at Hist[Loc]) uses bit 31 as a
    //  flag to indicate if a fourth element in the record exists - which would
    //  be used to store the highest 31 binary digits in the number of
    //  solutions for this record. (A record represents a board position)
    //  Bit 30 is used in a similar fashion to indicate if a third element in
    //  the record is needed to store the middle 31 bits of the solution count.
    //  The remaining 30 bits are used for the next link in the link list for
    //  the current Ptrn24low.

    //  The second array element in the record (at Hist[Loc+1]) uses bits 31 to
    //  23 to store the 9 highest bits of the "Score".
    //  (Ptrn9high holds the 9 highest bits of the current board pattern.)
    //  The remaining 23 bits are the 23 lowest bits in the number of solutions
    //  that exist from the current board position.

    //  If the number of solutions from the current position requires more than
    //  the above 23 bits, (bit 30 at Hist[Loc] is set), then a third array
    //  element is used (at Hist[Loc + 2]) to save the next 31 bits in the
    //  number of solutions..

    //  If the number of solutions is larger than the above 23 + 31
    //  bits (bit 31 at Hist[Loc] is set), then a fourth array element (at
    //  Hist[Loc+3] is used for the highest 31 bits in the number of solutions.

    //  Finally, despite the large size of the Hist[] array, for some start/end
    //  combinations, the array may overflow. If/when this happens, the HistHead
    //  array is reset to zeros (effectively erasing the Hist[] records), and
    //  the record writing starts from scratch - using the current Stack position.

unsigned Hist[MAX_HIST10];       //  Data for each board pattern.
unsigned HistHead[16777220];     //  Index for link lists into Hist[]
                                 //  (Equals 2^24 and change)
unsigned HistFree;               //  Next avail. loc for data.

    //  The TotPos and WinPos arrays count the total positions observed and
    //  the number of winning positions observed.

unsigned TotPos[36];
unsigned WinPos[36];

            //  The 76 possible moves are defined by the
            //  jump from, over, and to positions. "Next"
            //  speads up the search process by skiping
            //  to the next peg position.
int From[] = {0, 0, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 8, 8,
    9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 12, 12, 13, 14, 15, 15, 15, 15,
    16, 16, 16, 16, 17, 17, 17, 17, 18, 19, 20, 20, 21, 21,
    22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25,
    26, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32};

int Over[] = {1, 3, 4, 1, 5, 4, 8, 9, 4, 10, 7, 13, 8, 14, 3, 7, 9, 15,
    4, 8, 10, 16, 5, 9, 11, 17, 10, 18, 11, 19, 14, 15, 8, 14, 16, 22,
    9, 15, 17, 23, 10, 16, 18, 24, 17, 18, 13, 21, 14, 22,
    15, 21, 23, 27, 16, 22, 24, 28, 17, 23, 25, 29, 18, 24,
    19, 25, 22, 28, 23, 24, 28, 27, 31, 28, 29, 31};

int To[] = {2, 8, 9, 0, 10, 5, 15, 16, 3, 17, 8, 20, 9, 21, 0, 6, 10, 22,
    1, 7, 11, 23, 2, 8, 12, 24, 9, 25, 10, 26, 15, 16, 3, 13, 17, 27,
    4, 14, 18, 28, 5, 15, 19, 29, 16, 17, 6, 22, 7, 23,
    8, 20, 24, 30, 9, 21, 25, 31, 10, 22, 26, 32, 11, 23,
    12, 24, 15, 29, 16, 17, 27, 22, 32, 23, 24, 30};

int Next[] = {2, 2, 3, 5, 5, 7, 7, 8, 10, 10, 12, 12, 14, 14, 18, 18, 18, 18,
    22, 22, 22, 22, 26, 26, 26, 26, 28, 28, 30, 30, 31, 32, 36, 36, 36, 36,
    40, 40, 40, 40, 44, 44, 44, 44, 45, 46, 48, 48, 50, 50,
    54, 54, 54, 54, 58, 58, 58, 58, 62, 62, 62, 62, 64, 64,
    66, 66, 68, 68, 69, 71, 71, 73, 73, 74, 99, 99};

            //  For each unique board pattern, 7 other equivalent
            //  patterns exist due to rotations/reflections. The
            //  AltPos[][] table is used to generate these equivalent pos.
            //  These rotations/reflections are only used for total possible
            //  moves and not used to total winning combinations.
int AltPos[7][33] = {
    {20, 13, 6, 21, 14, 7, 30, 27, 22, 15, 8, 3, 0, 31, 28, 23, 16,
    9, 4, 1, 32, 29, 24, 17, 10, 5, 2, 25, 18, 11, 26, 19, 12},
    {32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18,
    17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
    {12, 19, 26, 11, 18, 25, 2, 5, 10, 17, 24, 29, 32, 1, 4, 9, 16,
    23, 28, 31, 0, 3, 8, 15, 22, 27, 30, 7, 14, 21, 6, 13, 20},
    {2, 1, 0, 5, 4, 3, 12, 11, 10, 9, 8, 7, 6, 19, 18, 17, 16, 15,
    14, 13, 26, 25, 24, 23, 22, 21, 20, 29, 28, 27, 32, 31, 30},
    {6, 13, 20, 7, 14, 21, 0, 3, 8, 15, 22, 27, 30, 1, 4, 9, 16,
    23, 28, 31, 2, 5, 10, 17, 24, 29, 32, 11, 18, 25, 12, 19, 26},
    {30, 31, 32, 27, 28, 29, 20, 21, 22, 23, 24, 25, 26, 13, 14,
    15, 16, 17, 18, 19, 6, 7, 8, 9, 10, 11, 12, 3, 4, 5, 0, 1, 2},
    {26, 19, 12, 25, 18, 11, 32, 29, 24, 17, 10, 5, 2, 31, 28, 23,
    16, 9, 4, 1, 30, 27, 22, 15, 8, 3, 0, 21, 14, 7, 20, 13, 6}};

int Occupied[36];                //  Holes that are occupied by pegs

unsigned SetBit[36];             //  Used to set bits.

int SolveForWins;                //  Flag for what user wants to solve for
int DispSolFlag;                 //  Will display a couple of solutions

char Databuff[20];               //  Used for user input

unsigned Ptrn9high, Ptrn24low;   //  Bits for lowest score for a board pos.
                                 //  (including rotations/reflections if applicable.)

unsigned SolLowBits, SolMidBits, SolHighBits;  //  Global variables for nbr. sol.
                                               //  from a given board pattern
unsigned SolE0, SolE9, SolE18;   //  Nbr. of Sol. expressed as
                                 //  base 10
unsigned NbrRec;                 //  Counts records (board positions)

int WorstGame = 25;              //  Optional use if looking for worst
                                 //  possible game.

int  SolHole, StartHole;         //  Solution / start holes
unsigned InitSolIdx;             //  Used to reinitialize the HistHead/Hist
                                 //  arrays.



int main(void) {

  int i;
  int StackPtr = 0;
  int StackPtr1 = 1;             //  Always = stackptr + 1.
  int TrialMove;
  unsigned HistLoc;              //  Loc. (if found) of record in Hist[].

  InitSys();                     //  Initialize system.
                                            //  Loop until StackPtr returns to 0.
  do {                                      //  Start search.
    TrialMove = StkMove[StackPtr1] + 1;     //  Will look for next possible move
    while (TrialMove < 76) {                //  Trial moves are 0 to 75.
      if (!Occupied[From[TrialMove]])       //  If no peg at jump from hole
        TrialMove = Next[TrialMove];        //  Next[] can skip other "no peg"
      else if (!Occupied[Over[TrialMove]])  //  If no peg to jump over
        TrialMove++;
      else if (Occupied[To[TrialMove]])     //  If jump to loc. is occupied...
        TrialMove++;
      else                                  //  Else next valid move
        break;                              //  has been found.
    }                                       //  Exits to here when either move
                                            //  was found or no valid move exists
    if (TrialMove < 76) {                   //  If a move was found...
      StkMove[StackPtr1] = TrialMove;
      Occupied[From[TrialMove]] = 0;        //  Update board
      Occupied[Over[TrialMove]] = 0;        //  for move.
      Occupied[To[TrialMove]] = 1;
                                            //  Calculate the lowest
      GetScore();                           //  score for this new position.

        //  Check the history data to see if this position (or
        //  any rotation/reflection) has been seen before. If yes,
        //  then nbr. of sol. from prior position can be directly
        //  used, and no further search of subtree is needed.
        //  Else not seen before and subtree search is required.

      HistLoc = CkHist();                   //  Gets record location if found,
                                            //  else equals zero.
      if (HistLoc) {                        //  If this position
        Occupied[From[TrialMove]] = 1;      //  has been seen
        Occupied[Over[TrialMove]] = 1;      //  before, restore
        Occupied[To[TrialMove]] = 0;        //  the board,
                                            //  and update nbr.
        GetSol(HistLoc);                    //  of solutions.
        StkLowBin[StackPtr] += SolLowBits;
        StkMidBin[StackPtr] += SolMidBits;
        StkHighBin[StackPtr] += SolHighBits;
        if (StkLowBin[StackPtr] & 0x800000) {   //  If carry above 23 bits
          StkLowBin[StackPtr] &= 0x7FFFFF;      //  Limit to 23 bits
          StkMidBin[StackPtr]++;                //  Add carry
        }
        if (StkMidBin[StackPtr] & 0x80000000) { //  If carry above 31 bits
          StkMidBin[StackPtr] &= 0x7FFFFFFF;    //  Limit to 31 bits
          StkHighBin[StackPtr]++;               //  Add carry
        }
      }
                                            //  Else position not seen
      else {                                //  before. Init stack pos.
        StackPtr++;                         //  for next iteration.
        StackPtr1++;                        //  Increment stack pointers.
        StkLowBin[StackPtr] = 0;            //  for continued search.
        StkMidBin[StackPtr] = 0;
        StkHighBin[StackPtr] = 0;
        Stk24low[StackPtr] = Ptrn24low;     //  Save score for
        Stk9high[StackPtr] = Ptrn9high;     //  later add to hist
        StkMove[StackPtr1] = -1;            //  Initialize "move" for next search
      }
    }

    //  Else end of new moves for this stack position. Update
    //  the known solution results and backtrack 1 level in stack.

    else {                                  //  Update history with this data
      if (!SolveForWins) {                  //  If solving for total positions
        if ((Ptrn24low == Stk24low[StackPtr]) && (Ptrn9high == Stk9high[StackPtr]))
          StkLowBin[StackPtr] = 1;
      }
      Stk2Hist(StackPtr);                   //  Store stack data in history
      TotPos[StackPtr]++;                   //  Counts total positions seen
      if ((StkLowBin[StackPtr]) ||          //  If at least one win found from this
            (StkMidBin[StackPtr]) ||        //  position, increment the number of
            (StkHighBin[StackPtr]))         //  winning positions for this number
        WinPos[StackPtr]++;                 //  of holes.
      TrialMove = StkMove[StackPtr];        //  Reverse this move
      Occupied[From[TrialMove]] = 1;        //  Restore prior
      Occupied[Over[TrialMove]] = 1;        //  peg position.
      Occupied[To[TrialMove]] = 0;
      StackPtr--;                           //  Decrement stack.
      StackPtr1--;
                                              //  Update stack sol. totals.
      StkLowBin[StackPtr] += StkLowBin[StackPtr1];
      StkMidBin[StackPtr] += StkMidBin[StackPtr1];
      StkHighBin[StackPtr] += StkHighBin[StackPtr1];
      if (StkLowBin[StackPtr] & 0x800000) {   //  If carry above 23 bits
        StkLowBin[StackPtr] &= 0x7FFFFF;      //  Limit to 23 bits
        StkMidBin[StackPtr]++;                //  Add carry
      }
      if (StkMidBin[StackPtr] & 0x80000000) { //  If carry above 31 bits
        StkMidBin[StackPtr] &= 0x7FFFFFFF;    //  Limit to 31 bits
        StkHighBin[StackPtr]++;               //  Add carry
      }

//    Optional code to find worst possible game.
/*
      if ((Stk24low[StackPtr1] == Ptrn24low) && (Stk9high[StackPtr1] == Ptrn9high)
            && (StackPtr1 < WorstGame)) {
        WorstGame = StackPtr1;
        puts("New worst game");
        for (i = 1; i <= StackPtr1; i++) {
          TrialMove = StkMove[i];
          printf("%d) Jump from %d to %d\n", i, From[TrialMove], To[TrialMove]);
        }
        PauseMsg();
      }
*/

    }

    if (StackPtr < 5) {                     //  Status report.
      for (i = 1; i <= StackPtr; i++) {
        TrialMove = StkMove[i];
        printf("\nStkMove[%d] =%3d     From: %2d   To: %2d\n",
            i, TrialMove, From[TrialMove], To[TrialMove]);
        printf("StkHighBin =%'13u   StkMidBin =%'14u   StkLowBin =%'10u\n",
            StkHighBin[i], StkMidBin[i], StkLowBin[i]);
      }
      printf("\nNbrRec = %'u     HistFree = %'u  (Will reset at %'u)\n\n",
        NbrRec, HistFree, MAX_HIST);
    }
  } while (StackPtr1);                      //  Repeat all combinations.

                    //    Output results.
  Bin2Dec(0);
  printf("\n\nResults for Start Hole = %d    Solution Hole = %d\n\n",
        StartHole, SolHole);
  if (SolveForWins)
    puts("Total possible wins:\n");
  else
    puts("Total possible games:");
  printf("      %12'u E+18\n", SolE18);
  printf("Plus  %12'u E+09\n", SolE9);
  printf("Plus  %12'u\n",SolE0);

  PauseMsg();
  if (SolveForWins)
    PosCount();                             //  Output position counts
}



//*****************************************************************************
//
//                                    InitSys
//
//*****************************************************************************

void InitSys(void) {

  unsigned bit2set;
  int i;

  puts("                      HI-Q");
  puts("             33 Hole Peg Solitaire");
  puts("                    Analysis\n");
  puts("                Computer Program");
  puts("                       by");
  puts("                  Bill Butler");

  puts("\nDo you want to solve for Total Wins (Enter \"W\")");
  puts("or for Total Games (Enter \"G\")");

  gets(Databuff);
  if (tolower(Databuff[0]) == 'w')
    SolveForWins = 1;
  else
    SolveForWins = 0;


  puts("Enter number of hole for initial space ( 0 to 32 )");
  gets(Databuff);
  StartHole = atoi(Databuff);

  puts("Enter number of hole for final peg ( 0 to 32 )");
  gets(Databuff);
  SolHole = atoi(Databuff);

  DispSolFlag = 0;                          //  Default = 0
  if (SolveForWins) {
    puts("Do you want to display any solutions?");
    puts("Enter \"1\" for Yes   or \"0\" for No");
    gets(Databuff);
    DispSolFlag = atoi(Databuff);
  }
                                            //  The SetBit[] array is
                                            //  used to translate board
                                            //  positions into bit positions.
  bit2set = 1;
  for (i = 0; i < 24 ; i++) {               //  The lowest 24 bits are
    SetBit[i] = bit2set;                    //  used to form the 24 bit
    bit2set <<= 1;                          //  index.
  }
  bit2set = 1;
  for (i = 24; i < 33 ; i++) {              //  The most significant
    SetBit[i] = bit2set;                    //  bits form the 9 bit
    bit2set <<= 1;                          //  remainder.
  }

  for (i = 0; i <= 32; i++)                 //  Set up initial board
    Occupied[i] = 1;
  Occupied[StartHole] = 0;

  GetScore();                               //  Get initial score
  Stk24low[1] = Ptrn24low;                  //   Initialize stack
  Stk9high[1] = Ptrn9high;
  StkMove[1] = -1;                          //  Setup for first move

                                            //  Set up solution record
  Hist[1] = 0;                              //  No links, no extra solution count
  if (SolHole < 24) {                       //  If sol hole is in the low bits
    Hist[2] = 1;                            //  The (9 high bits) = 0 + one solution
    InitSolIdx = SetBit[SolHole];
    HistHead[InitSolIdx] = 1;               //  Point to this record
  }
  else {                                    //  Else solution hole is in the high bits
    Hist[2] = (SetBit[SolHole] << 23) + 1;  //  Save the high 9 bits plus 1 sol.
    InitSolIdx = 0;
    HistHead[0] = 1;                        //  Point to this record.
  }

  HistFree = 3;                             //  Next avail. array location
  NbrRec = 1;                               //  One position is defined
}



//*****************************************************************************
//
//                                    GetScore
//
//  This routine converts the occupied positions of the board's 33 holes into
//  two numbers (Low24Bits and High9Bits). Since the board position has 7 other
//  equivalent evaluations due to rotations/reflections, numbers are also
//  calculated for these positions. The lowest of these becomes the "Score" for
//  the board position and is used for indexing into the history array.
//
//  Note: If solving for number of wins, the rotations/relections are not used.
//
//*****************************************************************************

void GetScore(void) {

  unsigned Low24Bits, High9Bits;
  int i, j;
  int EquivPos;

                                            //  First calculate the
  High9Bits = 0;                            //  current pattern.
  Low24Bits = 0;

  for (i = 32; i >= 24; i--) {              //  Process most significant
    if (Occupied[i])                        //  bits.
      High9Bits += SetBit[i];
  }

  for (i = 23; i >= 0; i--) {               //  Then least sig. bits.
    if (Occupied[i])
      Low24Bits += SetBit[i];
  }

  Ptrn9high = High9Bits;                    //  This is the lowest so far
  Ptrn24low = Low24Bits;

  if (SolveForWins)                         //  If solving for wins, don't use
    return;                                 //  alternate positions.

                                            //  Now calculate the same nbrs. for
                                            //  the 7 rotations/reflections.
  for (j = 6; j >= 0; j--) {
    High9Bits = 0;
    Low24Bits = 0;


    for (i = 32; i >= 24; i--) {
      EquivPos = AltPos[j][i];
      if (Occupied[EquivPos])               //  If a peg is at this location,
        High9Bits += SetBit[i];             //  then mark it.
    }
    for (i = 23; i >= 0; i--) {
      EquivPos = AltPos[j][i];
      if (Occupied[EquivPos])               //  Gets lowest 24 bits
        Low24Bits += SetBit[i];
    }
                                            //  Keep lowest score.
    if (High9Bits > Ptrn9high)
      continue;
    if (High9Bits < Ptrn9high) {            //  New low score.
      Ptrn9high = High9Bits;
      Ptrn24low = Low24Bits;
      continue;
    }
    if (Low24Bits < Ptrn24low)              //  If high 9 tied,
      Ptrn24low = Low24Bits;                //  use low bits to check.
  }
}



//*****************************************************************************
//
//                                    CkHist
//
//  This routine checks the history array to see if the pattern represented by
//  "Ptrn9high", "Ptrn24low" has been encountered before. If the pattern is already
//  in the arrays, then the index for its location is returned, else 0 is returned.
//
//*****************************************************************************

unsigned CkHist(void) {

  unsigned WorkBits, RecLoc;

        //  The lowest 24 bits of each score pattern are used as an index
        //  to a link list whose remaining 9 bits are stored in Hist[].

        //  Search until either a match is found or
        //  there are no more patterns in the link list.

  for (RecLoc = HistHead[Ptrn24low]; RecLoc;
         RecLoc = (Hist[RecLoc] & 0x3FFFFFFF)) {
    WorkBits = Hist[RecLoc + 1];    //  Gets value that contains the high 9 bits
    WorkBits >>= 23;                //  Shift the 9 bits into position.
    if (WorkBits == Ptrn9high)      //  If match then found.
      break;                        //  Exit loop with RecLoc at found loc.
  }                                 //  Else keep looking.
                                    //  Returns either found location
  return (RecLoc);                  //  or "0" if not found.
}



//*****************************************************************************
//
//                                    GetSol
//
//  This routine extracts the number of solutions associated with the history
//  pattern located at "ArrLoc". The result is placed in the global variables
//  SolLowBits, SolMidBits, SolHighBits.
//
//*****************************************************************************

void GetSol(unsigned ArrLoc) {

  unsigned WorkBits, HistLoc;

  HistLoc = ArrLoc;

  WorkBits = Hist[HistLoc++];               //  Get flags for mid and high portions
                                            //  Increment index to get low bits
  SolLowBits = Hist[HistLoc] & 0x7FFFFF;    //  Low bits are at bit 22 to bit 0
  SolMidBits = 0;                           //  Default is no middle bits.
  SolHighBits = 0;                          //  or high bits
  if (WorkBits & 0x40000000) {              //  If middle bits flag is set
    SolMidBits = Hist[++HistLoc];           //  then get middle bits
    if (WorkBits & 0x80000000)              //  If high bits flag is also set
      SolHighBits = Hist[++HistLoc];        //  Get high bits
  }
}


//*****************************************************************************
//
//                                    Stk2Hist
//
//  This routine creates a new record in the history array for the data at
//  StackLoc.
//
//  If the number of array locations exceeds the maximum limit. then the Hist[]
//  array and its HistHead[] are reinitialized.
//
//*****************************************************************************

void Stk2Hist(int StackLoc) {

  unsigned ArrLoc, LinkHead, NextLink;
  int i;

  NbrRec++;                                 //  Increment nbr. records in Hist[]
  LinkHead = Stk24low[StackLoc];            //  Start of L.L. for this Ptrn24low
  NextLink = HistHead[LinkHead];            //  This goes into [ArrLoc + 1]
  ArrLoc = HistFree;                        //  New record storage starts here
  HistHead[LinkHead] = ArrLoc;              //  New record is in link list

  Hist[++ArrLoc] = (Stk9high[StackLoc] << 23) //  High 9 bits of score plus
     + StkLowBin[StackLoc];                   //  23 lowest bits of nbr. sol.

  if (StkHighBin[StackLoc]) {                 //  If > 54 bits in nbr of sol.
    Hist[ArrLoc - 1] = 0xC0000000 + NextLink; //  Flags + next link in link list
    Hist[++ArrLoc] = StkMidBin[StackLoc];     //  Bits 24 to 54 in nbr. sol
    Hist[++ArrLoc] = StkHighBin[StackLoc];    //  Bits 55 and up in nbr. sol.
    HistFree += 4;                            //  Next avail. loc. in Hist[]
  }
  else if (StkMidBin[StackLoc]) {             //  Else if just > 23 bits in sol.
    Hist[ArrLoc - 1] = 0x40000000 + NextLink; //  Flag + next link in link list;
    Hist[++ArrLoc] = StkMidBin[StackLoc];
    HistFree += 3;
  }
  else {
    Hist[ArrLoc - 1] = NextLink;              //  Else just set up next link
    HistFree += 2;
  }

            //  If the History array is about to overflow, reinitialize it.
            //  Subsequent inquiries into the array will start posting board
            //  position info from scratch. Note that the solution totals that
            //  are kept on the stack will not be affected.

  if (HistFree > MAX_HIST) {
    for ( i = 16777215; i >= 0; i--)          //  Clear the HistHeads array
      HistHead[i] = 0;
    HistHead[InitSolIdx] = 1;                 //  Point to the solution record
    HistFree = 3;                             //  Will overwrite old records.
    NbrRec = 1;
  }

  if (DispSolFlag) {                          //  Optional display 1 or 2 solutions
    if ((StackLoc == 30) && (StkLowBin[30])) {
      puts("Solution (except last move)");
      for ( NextLink = 1; NextLink <= 30; NextLink++) {
        ArrLoc = StkMove[NextLink];
        printf(" %d -> %d,", From[ArrLoc], To[ArrLoc]);
      }
      PauseMsg();
    }
  }
}


//*****************************************************************************
//
//                                PosCount
//
//  This routine outputs the total number of positions seen and the total number
//  of winning positions seen. The counts only count "1" for any rotation/reflection.
//
//*****************************************************************************

void PosCount(void) {

  int i, TotalPos, TotalWin;
                                          //  Tree search doesn't vist the final
                                          //  winning position. Thus adjust the
                                          //  position and win totals for these
                                          //  conditions.
  TotPos[0] = 1;                          //  Start position
  TotPos[31] += 1;                        //  Adjust for not visiting win position
                                          //  If there was at least one win.
  if (StkLowBin[0] || StkMidBin[0] || StkHighBin[0]) {
    WinPos[0] = 1;                        //  Start position
    WinPos[31] = 1;                       //  Win position
  }

  TotalPos = 0;
  TotalWin = 0;

  puts(" Number        Total        Total Win");
  puts("of moves     Positions      Positions");

  for (i = 0; i <= 31; i++) {
    TotalPos += TotPos[i];
    TotalWin += WinPos[i];
    printf("%5d   %'14u  %'14u\n", i, TotPos[i], WinPos[i]);
    if (!(i%10))
    PauseMsg();
  }
  printf("Totals  %'14u  %'14u\n", TotalPos, TotalWin);

  PauseMsg();
}




//*****************************************************************************
//
//                                    Bin2Dec
//
//  This routine converts the 85 bit binary number that is in Stack[StackPos] to
//  base 10 numbers and places the result in global vars. SolE0, SolE9, SolE18
//
//*****************************************************************************

void Bin2Dec(int StackPos) {

  unsigned BinHigh, BinMid, BinLow;
  unsigned DecE18, DecE9, DecE0;        //  The result in decimal will be here
  unsigned IncrE18, IncrE9, IncrE0;     //  Used to calculate decimal equivalent
  unsigned OneBil = 1000000000;
  int i;

  BinHigh = StkHighBin[StackPos];       //  Get high binary to convert
  BinMid = StkMidBin[StackPos];         //  Get middle binary to convert
  BinLow = StkLowBin[StackPos];         //  Get low binary to convert

  DecE18 = 0;                           //  Initialize for calculations
  DecE9 = 0;                            //  Decimal result will be
  DecE0 = 0;                            //  constructed here.
  IncrE18 = 0;                          //  Initialize increments
  IncrE9 = 0;
  IncrE0 = 1;

  for (i = 1; i <= 23; i++) {           //  First convert the low bits
    if (BinLow & 1)                     //  If bit exists
      DecE0 += IncrE0;                  //  Increase the low total by "increment"
    IncrE0 += IncrE0;                   //  Double the increment
    BinLow >>= 1;                       //  Move next bit into position
  }                                     //  Only have to work with low numbers

  for (i = 1; i <= 31; i++) {           //  Get the middle portion of the number
    if (BinMid & 1) {                   //  If bit exists
      DecE0 += IncrE0;                  //  Increase the low total by "increment"
      DecE9 += IncrE9;                  //  Increase the middle total by increment
    }
    if (DecE0 >= OneBil) {              //  Low decimal number can only have
      DecE0 -= OneBil;                  //  9 digits. If overflow, subt. to keep
      DecE9++;                          //  at 9 didgits and add carry
    }
    IncrE0 += IncrE0;                   //  Double the increment
    IncrE9 += IncrE9;
    if (IncrE0 >= OneBil) {             //  Limit to 9 digits. Use carry if
      IncrE0 -= OneBil;                 //  too large.
      IncrE9++;
    }
    BinMid >>= 1;                       //  Move next bit into position
  }

  for (i = 1; i <= 31; i++) {           //  Get the high portion of the number
    if (BinHigh & 1) {                  //  If bit exists
      DecE0 += IncrE0;                  //  Increase the low total by "increment"
      DecE9 += IncrE9;                  //  Increase the middle portion by incr
      DecE18 += IncrE18;                //  Increase the high portion by incr
    }

    if (DecE0 >= OneBil) {              //  Low decimal number can only have
      DecE0 -= OneBil;                  //  9 digits. If overflow, subt. to keep
      DecE9++;                          //  at 9 digits and add carry
    }
    if (DecE9 >= OneBil) {              //  Mid decimal number can only have
      DecE9 -= OneBil;                  //  9 digits. If overflow, subt. to keep
      DecE18++;                         //  at 9 didgits and add carry
    }
    IncrE0 += IncrE0;                   //  Double the increment
    IncrE9 += IncrE9;
    IncrE18 += IncrE18;

    if (IncrE0 >= OneBil) {             //  Limit to 9 digits. Use carry if
      IncrE0 -= OneBil;                 //  too large.
      IncrE9++;
    }

    if (IncrE9 >= OneBil) {             //  Limit to 9 digits. Use carry if
      IncrE9 -= OneBil;                 //  too large.
      IncrE18++;
    }
    BinHigh >>= 1;                      //  Move next bit into position
  }

  SolE0 = DecE0;                        //  Copy to global variables
  SolE9 = DecE9;
  SolE18 = DecE18;
}



//*****************************************************************************
//
//                            Misc. Functions
//
//*****************************************************************************

void PauseMsg(void) {

  puts("\nPress \"Enter\" to continue\n");
  gets(Databuff);
}




Return to the main Peg 33 Solitaire page

Return to Durango Bill's Home page


Web page generated via Sea Monkey's Composer HTML editor
within  a Linux Cinnamon Mint 18 operating system.
(Goodbye Microsoft)