//*****************************************************************************
//
// peg33breadth.c
//
// This program counts the number of solutions to the 33 hole peg solitaire
// 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 (17 * ARRAY_MAX + 8 * 2^25) bytes of RAM).
//
//*****************************************************************************
#include <stdheaders.h> // The usual stdio.h, etc.
#define ARRAY_MAX 56000000 // Maximum number of elements in the
// "positions" data arrays.
#define ONEBILLION 1000000000
// Define procedures.
void InitSys(void); // Initialize system. Get user data.
void Pegs2bits(void); // Change peg positions to bit patterns.
void Bits2pegs(void); // Change bit patterns to peg positions.
unsigned SearchPos(void); // Find & recognize board/peg patterns.
void BoardTotals(void); // Output Dead-End data.
void CommaNbr(char *); // Put commas in numbers.
void PauseMsg(void); // Pause the program
// 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 "Left8bits" and a "Right25bits". The
// "Right25bits" portion is used as a hash index for data storage.
unsigned Left8bits, Right25bits; // 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 "Right25bits" is
// connected in a common link list where "Right25bits" is used as an index
// into "NewHeads[]" and/or "OldHeads[]".
// For each board position,
// 1) Left8[] has the remaining 8 bits of the board position
// 2) NextLink[] contains the index ptr to the next "position" in the chain
// that shares the same Right25bits.
// 3) NbrCombHigh[] + NgrCombLow[] is the number of potential move
// combinations that can reach this position.
unsigned char Left8[ARRAY_MAX];
unsigned NextLink[ARRAY_MAX];
long long NbrCombHigh[ARRAY_MAX]; // NbrComb is split into two sections
unsigned NbrCombLow[ARRAY_MAX];
unsigned OldHeads[33554436]; // Use Right25bits as an index to positions
unsigned NewHeads[33554436]; // Equals 2^25 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 overwriting "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
long long 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[60]; // Used for user input
char CommaBuff[60]; // Both are used for putting commas in numbers
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
long long NbrWinsHigh;
unsigned NbrWinsLow;
double StartTime, ElapsedTime;
InitSys(); // Initialize system
StartTime = (double) clock() / CLOCKS_PER_SEC;
NbrWinsHigh = 0L;
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 = 33554431; i >= 0; i--) { // Copy link heads 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 <= 33554431; i++) { // For all link heads
// If old records exist, then process the
OldRecLoc = OldHeads[i]; // entire link list.
while (OldRecLoc) {
Right25bits = i; // Set up the board position for this old record
Left8bits = Left8[OldRecLoc];
Bits2pegs();
if (round == 32) { // Output board info for all single hole pos.
printf("\nOn the last round a single peg can exist at hole:");
for (DeadEndFlag = 0; DeadEndFlag <= 32; DeadEndFlag ++) {
if (PegPos[DeadEndFlag])
printf(" %d", DeadEndFlag);
}
sprintf(DataBuff, "%Ld", NbrCombHigh[OldRecLoc]);
CommaNbr(DataBuff);
sprintf(CommaBuff, "%u", NbrCombLow[OldRecLoc]);
CommaNbr(CommaBuff);
printf("\nNumber of ways to win at this position = %s E+9 + %s\n",
DataBuff, CommaBuff);
}
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 Left8bits & Right25bits 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]++;
}
}
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 Right25bits
NextLink[NewRecLoc] = NewHeads[Right25bits];
NewHeads[Right25bits] = NewRecLoc;
// Init rest of data for this new record
Left8[NewRecLoc] = Left8bits;
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++;
}
}
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;
}
}
SaveLoc = OldRecLoc; // Return the space of this
// old record 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 records for OldHeads[i]
} // End of all old records for this round
BoardPos[round] = PosCount; // Total board positions seen this round
sprintf(DataBuff, "%u", BoardPos[round]);
CommaNbr(DataBuff);
printf("\nOn round %d found %s peg patterns\n", round, DataBuff);
sprintf(DataBuff, "%u", MaxCombUsed);
CommaNbr(DataBuff);
printf(" Largest number of records in NbrComb[] was %s\n", DataBuff);
sprintf(DataBuff, "%u", ARRAY_MAX);
CommaNbr(DataBuff);
printf(" Overflow if >= %s\n", DataBuff);
if(round > 30)
puts("");
}
ElapsedTime = (double) clock() / CLOCKS_PER_SEC - StartTime;
printf("\nElapsed time = %g seconds\n", ElapsedTime);
printf("\n\nResults for starting hole = %d and ending hole %d\n", StartHole, SolPeg);
sprintf(DataBuff, "%Ld", NbrWinsHigh);
CommaNbr(DataBuff);
sprintf(CommaBuff, "%u", NbrWinsLow);
CommaNbr(CommaBuff);
printf("Total solutions found = %s E+9 + %s\n\n", DataBuff, CommaBuff);
PauseMsg();
BoardTotals(); // Output results for individual 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 "Left8bits" and "Right25bits"
for (i = ARRAY_MAX - 2, j = i + 1; i; i--, j--)
NextLink[i] = j; // Set up link list of available elements
NewHeads[Right25bits] = 1; // Location for start position
Left8[1] = Left8bits; // Rest of bit pattern for start position
NextLink[1] = 0; // End of this link list
NbrCombHigh[1] = 0L;
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 "Left8bits" and "Right25 bits".
//
//*****************************************************************************
void Pegs2bits(void) {
unsigned LeftBits, RightBits;
int i;
LeftBits = 0;
RightBits = 0;
for (i = 32; i > 24; i--) { // Process most significant
LeftBits <<= 1; // bits. Make room for next bit
LeftBits += PegPos[i];
}
for (i = 24; i >= 0; i--) { // Then least significant bits.
RightBits <<= 1;
RightBits += PegPos[i];
}
Left8bits = LeftBits; // The most significant 8 bits
Right25bits = RightBits; // The least significant 25 bits
}
//************************************************************************
//
// Bits2pegs
//
// This routine uses the 2 variables "Left8bits" and "Right25bits"
// to set up a valid board position in PegPos[].
//
//************************************************************************
void Bits2pegs(void) {
unsigned LeftBits, RightBits;
int i;
LeftBits = Left8bits;
RightBits = Right25bits;
for (i = 0; i <= 24; i++) { // Process least significant
PegPos[i] = (RightBits & 1); // bits.
RightBits >>= 1; // Next bit into position
}
for (i = 25; 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 "Left8bits", "Right25bits" 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 SearchPos(void) {
unsigned RecLoc;
// The lowest 25 bits of each board pattern are used as an index
// to a link list whose remaining 8 bits are stored in Left8[].
// Search until either a match is found or
// there are no more patterns in the link list.
for (RecLoc = NewHeads[Right25bits]; RecLoc; RecLoc = NextLink[RecLoc])
if (Left8[RecLoc] == Left8bits) // "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;
long long TotDeadEndsHigh;
unsigned TotDeadEndsLow;
BoardPos[0] = 1; // Starting position
TotPos = 0;
TotDeadEndsHigh = 0L;
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++;
}
sprintf(DataBuff, "%Ld", DeadEndsHigh[j]);
CommaNbr(DataBuff);
sprintf(CommaBuff, "%d", DeadEndsLow[j]);
CommaNbr(CommaBuff);
printf("There are %15s E9 + %12s deadend combinations on move %d\n",
DataBuff, CommaBuff, i);
}
sprintf(DataBuff, "%d", TotPos);
CommaNbr(DataBuff);
printf("\nTotal board positions for the game = %s\n", DataBuff);
sprintf(DataBuff, "%Ld", TotDeadEndsHigh);
CommaNbr(DataBuff);
sprintf(CommaBuff, "%d", TotDeadEndsLow);
CommaNbr(CommaBuff);
printf("Total possible games = %s E9 + %s\n\n", DataBuff, CommaBuff);
}
//******************************************************************************
//
// CommaNbr
//
// This routine places positional commas in the ASCI number that is in the
// array pointed to by the passed parameter. The number may optionally be
// preceded by a "-" sign and may optionally have trailing decimal digits.
// It is assumed that the array has at least 40 elements.
//
//******************************************************************************
void CommaNbr( char *TheArray) {
int FirstDigitLoc, LastDigitLoc, i, j, k,DigitCount;
if (TheArray[0] == '-')
FirstDigitLoc = 1;
else
FirstDigitLoc = 0;
i = FirstDigitLoc;
while(isdigit(TheArray[++i])); // Get location of last digit
LastDigitLoc = i - 1;
// For all digits in the number
for (i = LastDigitLoc, DigitCount = 1; i > FirstDigitLoc; i--, DigitCount++) {
if (!(DigitCount%3 )) { // If comma should go here,
for (j = 35, k = 36; j >= i; j--, k--) // Move everything to the right one space
TheArray[k] = TheArray[j];
TheArray[i] = ',';
}
}
}
//*****************************************************************************
//
// 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)