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



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

//
//                               NewHI_Q.C
//
//  This program counts the number of solutions to the "Hi-Q" peg game. The user
//  may enter any starting position for the initial hole and also any position
//  for the final peg.
//
//  The program uses a "breadth first" search
//
//  For each of 31 moves/rounds, the algorithm starts with a known number of
//  possible positions that can be reached in a known number of moves,
//  and then finds all possible positions that can be reached in all
//  possible moves on the next move/round.
//
//  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 "ARRAY_MAX" defines the amount of array space (and RAM) that the
//  program uses. (Major arrays use (20 * ARRAY_MAX + 8 * 2^24) bytes of RAM).
//
//*****************************************************************************


#include <stdheaders.h>            //  The usual stdio.h, etc.
#define ARRAY_MAX 70000000         //  Maximum number of elements in the
                                   //  "positions" data arrays. Probably
                                   //  won't need this much.
#define ONEBILLION 1000000000
                                   //  Define proceedures
void InitSys(void);
void Pegs2bits(void);
void Bits2pegs(void);
unsigned SearchPos(void);
void BoardTotals(void);
void PauseMsg(void);

    //  For data storage, the 33 holes of the peg board are condensed to a "33
    //  digit" binary number where a "1" indicates that a peg is present and a
    //  "0" indicates no peg at the position. The "33 digit" binary number is
    //  split into two components - a "Left9bits" and a "Right24bits". The
    //  "Right24bits" portion is used as a hash index for data storage.

unsigned Left9bits, Right24bits;    //  Bits represent the holes in the board.

    //  All peg board positions (and relevant data) are stored in the positions
    //  arrays. Each board position that shares a common "Right24bits" is
    //  connected in a common link list where "Right24bits" is used as an index
    //  into "NewHeads[]" and/or "OldHeads[]".
    //  For each board position,
    //  1) Left9[] has the remaining 9 bits of the board position
    //  2) NextLink[] contains the index ptr to the next "position" in the chain
    //  3) NbrComb[] is the number of potential move combinations that can reach
    //  this position.

unsigned Left9[ARRAY_MAX];         //  This could be unsigned short to save RAM
unsigned NextLink[ARRAY_MAX];
double NbrCombHigh[ARRAY_MAX];     //  NbrComb is split into two sections
unsigned NbrCombLow[ARRAY_MAX];
unsigned OldHeads[16777220];       //  Use Right24bits as an index to positions
unsigned NewHeads[16777220];       //  Equals 2^24 and change

    //  For each of the 32 rounds, the link heads at NewHeads[] are copied to
    //  OldHeads[] with NewHeads[] initialized to zero. Thus OldHeads[] is used
    //  to find board positions as of "last round" while NewHeads[] is used to
    //  generate and index new board positions on the following round. Note,
    //  the last of the "32" rounds is a dummy as the game stops after 31 moves.

    //  After the program has been initialized there is one record/position in
    //  the above arrays that represents the starting position. On each of the
    //  subsequent 32 rounds of trial jumps, all "old" (current board) positions
    //  are used to generate all possible "new" positions for the next round.
    //  After an "old" position is no longer needed, its space is overwritten
    //  by "new" positions. The practice of overwritting "old" positions with
    //  "new" positions saves array space as compared to maintaining separate
    //  "old" and "new" positions arrays. The allocation of elements in these
    //  arrays is managed by a master link list.)

unsigned BoardPos[36];             //  Count board positions this round
double DeadEndsHigh[36];           //  Number of dead ends each round. Total
unsigned DeadEndsLow[36];          //  equals total possible games. Note:
                                   //  A Dead End in round "N" is tabulated in
                                   //  index position "N + 1"

unsigned PosAvail;                 //  Pts. to next available pos. in master LL.

    //  For 32 rounds of possible jumps (Last iteration just counts final dead ends)
    //    For each of the "old" positions (includes total moves to get to these pos.)
    //      Try all possible next moves (There are 76 possible moves subject to peg pos.)
    //      Each time a move can be made, update the "new" data in the arrays.
    //    Repeat for all old records/positions.
    //  Repeat for all 32 rounds of possible jumps



    //  The 76 possible jump moves are defined by the From[], Over[], and To[] arrays.

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};


    //  Holes that are occupied by pegs.

int PegPos[36];                     //  Occupied = 1, empty = 0


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

int StartHole, SolPeg;              //  Start and end conditions
int AvailUsed, MaxCombUsed;         //  Status for max used pos in NbrComb[]



int main(void) {

  int round, i, OldRecLoc, TrialMove, NewRecLoc, SaveLoc;
  int DeadEndFlag;
  unsigned PosCount;                       //  Counts board positions each round

  double NbrWinsHigh;
  unsigned NbrWinsLow;

  InitSys();                               //  Initialize system

  NbrWinsHigh = 0.0;
  NbrWinsLow = 0;

  for (round = 1; round <= 32; round++) {  //  Loop for 32 trial rounds. Last
                                           //  round just counts final dead ends
    MaxCombUsed = 0;                       //  Track max elements used in NbrComb[]
    PosCount = 0;                          //  Count number of positions each round

    for (i = 16777215; i >= 0; i--) {      //  Copy linkheads from the "new" positions
      OldHeads[i] = NewHeads[i];           //  to the old positions and set up the "new"
      NewHeads[i] = 0;                     //  link heads for the new positions
    }

    for (i = 0; i <= 16777215; i++) {      //  For all link heads
                                           //  If old records exist, then process the
      OldRecLoc = OldHeads[i];             //  entire link list.
      while (OldRecLoc) {
        Right24bits = i;                   //  Set up the board postion for this old record
        Left9bits = Left9[OldRecLoc];
        Bits2pegs();
        if (round == 32) {                 //  Output board info for all single hole pos.
          printf("On the last round a single peg can exist at hole:");
          for (DeadEndFlag = 0; DeadEndFlag <= 32; DeadEndFlag ++) {
            if (PegPos[DeadEndFlag])
              printf(" %d", DeadEndFlag);
          }
          puts("");
        }

        DeadEndFlag = 1;                   //  Try all 76 possible moves for this position
        for (TrialMove = 0; TrialMove < 76; TrialMove++) {
          if (!PegPos[From[TrialMove]])    //  If no peg at hole...
            continue;                      //  try next trial move
          if (!PegPos[Over[TrialMove]])    //  If no peg to jump over
            continue;                      //  try next trial move
          if (PegPos[To[TrialMove]])       //  If jump to loc. is occupied...
            continue;                      //  try next trial move

          DeadEndFlag = 0;                 //  If to here, a valid move has been found
          PegPos[From[TrialMove]] = 0;     //  Update board for this new position
          PegPos[Over[TrialMove]] = 0;
          PegPos[To[TrialMove]] = 1;
          Pegs2bits();                     //  Get Left9bits & Right24bits for
                                           //  this position

          NewRecLoc = SearchPos();         //  See if this position has been seen before
          if (NewRecLoc) {                 //  If record exists then just update NbrComb[]
            NbrCombHigh[NewRecLoc] += NbrCombHigh[OldRecLoc];
            NbrCombLow[NewRecLoc] += NbrCombLow[OldRecLoc];
            if (NbrCombLow[NewRecLoc] >= ONEBILLION) {
              NbrCombLow[NewRecLoc] -= ONEBILLION;
              NbrCombHigh[NewRecLoc] += 1.0;
            }
          }
          else {                           //  Else start a new record
            PosCount++;
            AvailUsed++;                   //  Use another record position
            if (AvailUsed > MaxCombUsed)   //  Keep track of max for overflow warning
              MaxCombUsed = AvailUsed;
            NewRecLoc = PosAvail;          //  Location for this new record
            if (!NewRecLoc) {
              puts("Position arrays are overflowing. Program will end.");
              exit(1);
            }
            PosAvail = NextLink[NewRecLoc];    //  Master list is updated
                                           //  Insert in link list for this Right24bits
            NextLink[NewRecLoc] = NewHeads[Right24bits];
            NewHeads[Right24bits] = NewRecLoc;
                                           //  Init rest of data for this new record
            Left9[NewRecLoc] = Left9bits;
            NbrCombHigh[NewRecLoc] = NbrCombHigh[OldRecLoc];
            NbrCombLow[NewRecLoc] = NbrCombLow[OldRecLoc];
          }

          if ((round == 31) && (PegPos[SolPeg])) {
            NbrWinsHigh += NbrCombHigh[OldRecLoc];
            NbrWinsLow += NbrCombLow[OldRecLoc];
            if (NbrWinsLow >= ONEBILLION) {
              NbrWinsLow -= ONEBILLION;
              NbrWinsHigh += 1.0;
            }
          }

          PegPos[From[TrialMove]] = 1;     //  Restore board position
          PegPos[Over[TrialMove]] = 1;
          PegPos[To[TrialMove]] = 0;

        }                                  //  End TrialMove loop
        if (DeadEndFlag) {                 //  If no moves were found
          DeadEndsHigh[round] += NbrCombHigh[OldRecLoc];
          DeadEndsLow[round] += NbrCombLow[OldRecLoc];
          if (DeadEndsLow[round] >= ONEBILLION) {
            DeadEndsLow[round] -= ONEBILLION;
            DeadEndsHigh[round] += 1.0;
          }
        }
                                            //  Return the space of this olr record
        SaveLoc = OldRecLoc;                //  to PosAvail
        OldRecLoc = NextLink[OldRecLoc];    //  Set up for next old record
        NextLink[SaveLoc] = PosAvail;       //  Restore to available list
        PosAvail = SaveLoc;
        AvailUsed--;                        //  Subtract one from number of records used
      }                                     //  End of recods for OldHeads[i]
    }                                       //  End of all old records for this round

    BoardPos[round] = PosCount;             //  Total board positions seen this round

    printf("\nOn round %d  found %'u board positions\n", round, BoardPos[round]);
    printf("     Largest number of records in NbrComb[] was %'u\n", MaxCombUsed);
    printf("     Overflow if >= %'d\n", ARRAY_MAX);
  }                                         //  Repeat for 32 rounds

  printf("\n\nResults for starting hole = %d  and ending hole %d\n", StartHole, SolPeg);
  printf("Total solutions found = %'.0f E+9  + %'u\n\n", NbrWinsHigh, NbrWinsLow);
  PauseMsg();
  BoardTotals();                            //  Output results for indidual rounds
  return(0);
}                                           //  End of program



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

void InitSys(void) {

  int i, j;

  puts("\nEnter number of hole for initial space (0 - 32)");
  gets(Databuff);
  StartHole = atoi(Databuff);

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

  for (i = 0; i <= 32; i++)           //  Set up start position
    PegPos[i] = 1;
  PegPos[StartHole] = 0;

  Pegs2bits();                        //  Get bit patterns for start position
                                      //  Sets up "Left9bits" and "Right24bits"

  for (i = ARRAY_MAX - 2, j = i + 1; i; i--, j--)
    NextLink[i] = j;                  //  Set up link list of available elements

  NewHeads[Right24bits] = 1;          //  Location for start position
  Left9[1] = Left9bits;               //  Rest of bit pattern for start position
  NextLink[1] = 0;                    //  End of this link list
  NbrCombHigh[1] = 0.0;
  NbrCombLow[1] = 1;                  //  Default of 1.

  PosAvail = 2;                       //  Start of available new positions
  AvailUsed = 1;                      //  One record position has been used

    //    Note: system initialization sets everything else to zero before
    //    this routine is called.
}



//*****************************************************************************
//
//                                Pegs2bits
//
//  This routine translates the occupied positions of the board's 33 holes
//  into two numbers "Left9bits" and "Right24 bits".
//
//*****************************************************************************

void Pegs2bits(void) {

  unsigned LeftBits, RightBits;
  int i;

  LeftBits = 0;
  RightBits = 0;

  for (i = 32; i > 23; i--) {        //  Process most significant
    LeftBits <<= 1;                  //  bits. Make room for next bit
    LeftBits += PegPos[i];
  }

  for (i = 23; i >= 0; i--) {        //  Then least significant bits.
    RightBits <<= 1;
    RightBits += PegPos[i];
  }


  Left9bits = LeftBits;              //  The most significant 9 bits
  Right24bits = RightBits;           //  The least significant 24 bits
}



//************************************************************************
//
//                            Bits2pegs
//
//  This routine uses the 2 variables "Left9bits" and "Right24bits"
//  to set up a valid board position in PegPos[].
//
//************************************************************************

void Bits2pegs(void) {

  unsigned LeftBits, RightBits;
  int i;

  LeftBits = Left9bits;
  RightBits = Right24bits;

  for (i = 0; i <= 23; i++) {       //  Process least significant
    PegPos[i] = (RightBits & 1);    //  bits.
    RightBits >>= 1;                //  Next bit into position
  }

  for (i = 24; i <= 32; i++) {      //  Then most sig. bits.
    PegPos[i] = (LeftBits & 1);
    LeftBits >>= 1;                 //  Next bit into position
  }
}



//*****************************************************************************
//
//                               SearchPos
//
//  This routine checks the position arrays to see if the "new" pattern
//  represented by "Left9bits", "Right24bits" has been encountered before.
//  If the pattern is already in the arrays, then the index for its locaton
//  is returned, else 0 is returned.
//
//*****************************************************************************

unsigned SearchPos(void) {

  unsigned RecLoc;

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

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

  for (RecLoc = NewHeads[Right24bits]; RecLoc; RecLoc = NextLink[RecLoc])
    if (Left9[RecLoc] == Left9bits)    // "break" executes if found
      break;                           //  Else keep looking.
                                       //  Returns either found location
  return (RecLoc);                     //  or "0" if not found.
}



//**********************************************************************
//
//                             BoardTotals
//
//  At the end of all the iterations output the number of dead ends and
//  total board positions seen on each round.
//
//**********************************************************************

void BoardTotals(void) {

  int i, j;
  unsigned TotPos;
  double TotDeadEndsHigh;
  unsigned TotDeadEndsLow;

  BoardPos[0] = 1;                            //  Starting position
  TotPos = 0;
  TotDeadEndsHigh = 0.0;
  TotDeadEndsLow = 0;
  for (i = 0, j = 1; i <= 31; i++, j++) {
    TotPos += BoardPos[i];                    //  Get grand totals
    TotDeadEndsHigh += DeadEndsHigh[j];
    TotDeadEndsLow += DeadEndsLow[j];
    if (TotDeadEndsLow >= ONEBILLION) {
      TotDeadEndsLow -= ONEBILLION;
      TotDeadEndsHigh += 1.0;
    }
    printf("There are %'17.0f E9 + %11'u deadend combinations after move %d\n",
           DeadEndsHigh[j], DeadEndsLow[j], i);
  }

  printf("\nTotal board positions for the game = %'u\n", TotPos);
  printf("Total possible games = %'.0f E9 + %'u\n", TotDeadEndsHigh, TotDeadEndsLow);
  PauseMsg();
}



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

void PauseMsg(void) {

  puts("Press \"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)