//************************************************************************************************* // // Peg33depth.c // // This program counts the number of solutions to the 33 hole peg solitaire game, // // The algorithm tries all possible move combinations and saves the resulting // board position after each subtree search is complete. These positions can then // be subsequently recognized, and their results can be 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 History[] array uses. // // As it currently configured, the program requires 3 GB of free RAM. // // 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. // // Start/stop Elapsed HistFree Elapsed HistFree // hole Time (Wins) at end Time (Games) at end // 0 206.772 421,528,967 214.731 484,943,661 // 1 94.6781 221,556,891 100.090 249,548,924 // 3 197.260 400,247,101 203.870 459,929,084 // 4 125.482 273,660,509 130.719 310,762,168 // 8 297.330 558,308,621 313.281 635,696,158 // 9 217.903 420,253,271 227.722 487,010,233 // 16 192.766 377,251,521 202.591 436,024,066 // //************************************************************************************************* #include // The usual headers #define MAX_HISTORY 636000000 // Upper limit to nbr of elements in the History[] array. // 636,000,000 needed for games with start hole = 8 // Define functions void InitSys(void); // User input and initialization void GetPtrns8and25(void); // Calculates Ptrn8high, Ptrn25low from peg positions unsigned ChkHist(void); // Checks to see if current board seen before in History[] void GetSol(unsigned); // Get nbr of sol. from History[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 CommaNbr(char *); // Puts commas in numbers 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 StkBits0to21[36]; // Nbr of Sol - lowest 22 binary digits unsigned StkBits22to52[36]; // Nbr of Sol - middle 31 binary digits unsigned StkBits53to84[36]; // Nbr of Sol - highest 32 binary digits unsigned Stk25low[36]; // The 25 low (index) bits for the peg positions. unsigned Stk8high[36]; // The remaining 8 high bits for the peg positions. // Bit representation of the current 33 hole board pos. // 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 8 bits of the board pattern (Stk8high[]), the number of solutions // found for this pattern, and a link to the next record that shares the // same index link (Ptrn25low). The 25 low bits of the board pattern 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 History[Loc]) contains the link to // the next record (in the link list) that shares the same 25 bit pattern. // // The second element in a record (at History[Loc+1]) uses: // Bits 30 and 31 indicate how many extra elements are needed for the NbrSol. // Bits 8 to 29 are used for the lowest 22 bits of the Nbr. of Solutions. // Bits 0 to 7 are used for the high bits of the peg position. // // If 3rd and 4th elements are needed (at History[Loc+2], History[Loc+3]), // they contain: // bits 22 to 52 of number of solutions (or games), // bits 53 to 84 of number of solutions (or games). // respectively for the number of solutions. (1, or 2 of these will be // used if needed.) // unsigned * History; // Data for each board pattern. unsigned * HistHead; // Index for link lists into History[] // Will be 33554432 elements (equals 2^25) unsigned HistFree; // Next avail. loc for data in History[]. // 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 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}; int PegPos[36]; // Holes that are occupied by pegs int SolveForWins; // Flag for what user wants to solve for int DispSolFlag; // Will display a couple of solutions char DataBuff[40]; // Used for user input and to put commas in numbers char CommaBuff1[40]; // Used to insert commas in numbers char CommaBuff2[40]; // Used to insert commas in numbers unsigned Ptrn8high, Ptrn25low; // Reduces board positions to bit sequences. unsigned SolBits0to21; // Global variables for number of games or wins unsigned SolBits22to52; unsigned SolBits53to84; // Global variables for nbr. sol. from a given // board pattern unsigned SolE0; // Nbr. of games or wins expressed using base 10 unsigned SolE9; unsigned SolE18; unsigned NbrRec; // Counts records (board positions) in History[] int SolHole, StartHole; // Solution hole, start hole int main(void) { int i; int StackPtr = 0; int StackPtr1 = 1; // Always = stackptr + 1. int TrialMove; unsigned HistLoc; // Location of record in History[]. // or "0" if not found double StartTime, ElapsedTime; // Keeps track of time to run the program. InitSys(); // Initialize system. StartTime = (double) clock() / CLOCKS_PER_SEC; // Loop until StackPtr returns to 0. do { // Start search. ("do while" loop) TrialMove = StkMove[StackPtr1] + 1; // Tests for next possible move while (TrialMove < 76) { // Trial moves are 0 to 75. if (!(PegPos[From[TrialMove]])) // If no peg at jump from hole TrialMove++; else if (!PegPos[Over[TrialMove]]) // If no peg to jump over TrialMove++; else if (PegPos[To[TrialMove]]) // If jump to loc. is occupied... TrialMove++; else // Else next valid move break; // has been found. } // Exits to here when either a move // was found or no valid move exists. // If no trial move, control exits to // "Else end of trial moves for // this stack position" if (TrialMove < 76) { // If a move was found... StkMove[StackPtr1] = TrialMove; PegPos[From[TrialMove]] = 0; // Update board PegPos[Over[TrialMove]] = 0; // for move. PegPos[To[TrialMove]] = 1; GetPtrns8and25(); // High 8 and low 25 bit patterns // for the current board position. // Check the history data to see if this position has been // seen before. If yes, then nbr. of games (or wins) from prior position // can be directly read from History[], and no further search of subtree is // needed. Else not seen before and subtree search is required. HistLoc = ChkHist(); // Gets record location if found, // else equals zero. if (HistLoc) { // If this position has been seen before... // Optional display solution if (DispSolFlag && (StackPtr == 30) && (To[TrialMove] == SolHole)) { puts("Found a solution"); for (i = 1; i <= 30; i++) printf(" %2d) %2d to %2d\n", i, From[StkMove[i]], To[StkMove[i]]); printf(" 31) %2d to %2d\n", From[TrialMove], To[TrialMove]); PauseMsg(); } // Position has been seen before. // Thus backtrack out of trial move. PegPos[From[TrialMove]] = 1; // Restore the board PegPos[Over[TrialMove]] = 1; // and update nbr. of solutions. PegPos[To[TrialMove]] = 0; GetSol(HistLoc); StkBits0to21[StackPtr] += SolBits0to21; // Update number of wins (or games) StkBits22to52[StackPtr] += SolBits22to52; StkBits53to84[StackPtr] += SolBits53to84; if (StkBits0to21[StackPtr] >= 0x400000) { // If carry above 22 bits StkBits0to21[StackPtr] -= 0x400000; // Limit to 22 bits StkBits22to52[StackPtr]++; // Add carry } if (StkBits22to52[StackPtr] >= 0x80000000) { // If carry above 31 bits StkBits22to52[StackPtr] -= 0x80000000; // Limit to 31 bits StkBits53to84[StackPtr]++; // Add carry } } // Else position not seen else { // before. Init stack pos. StackPtr++; // for next iteration. StackPtr1++; // Increment stack pointers. StkBits0to21[StackPtr] = 0; // for continued search. StkBits22to52[StackPtr] = 0; StkBits53to84[StackPtr] = 0; Stk25low[StackPtr] = Ptrn25low; // Save bit patterns for Stk8high[StackPtr] = Ptrn8high; // later add to hist StkMove[StackPtr1] = -1; // Initialize "move" for next search } } // End of "if a trial move was found" // Else, end of trial 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 games if ((Ptrn25low == Stk25low[StackPtr]) && (Ptrn8high == Stk8high[StackPtr])) StkBits0to21[StackPtr] = 1; // Found a game a game position but not a win } Stk2Hist(StackPtr); // Store stack data in history TotPos[StackPtr]++; // Counts total positions seen if (StkBits0to21[StackPtr] || // If at least one win found from this StkBits22to52[StackPtr] || // position, increment the number of StkBits53to84[StackPtr]) // winning positions for this number of holes. WinPos[StackPtr]++; // Backtrack TrialMove = StkMove[StackPtr]; // Reverse this move PegPos[From[TrialMove]] = 1; // Restore prior PegPos[Over[TrialMove]] = 1; // peg position. PegPos[To[TrialMove]] = 0; StackPtr--; // Decrement stack. StackPtr1--; // Update stack sol. totals. StkBits0to21[StackPtr] += StkBits0to21[StackPtr1]; StkBits22to52[StackPtr] += StkBits22to52[StackPtr1]; StkBits53to84[StackPtr] += StkBits53to84[StackPtr1]; if (StkBits0to21[StackPtr] >= 0x400000) { // If carry above 22 bits StkBits0to21[StackPtr] -= 0x400000; // Limit to 22 bits StkBits22to52[StackPtr]++; // Add carry } if (StkBits22to52[StackPtr] >= 0x80000000) { // If carry above 31 bits StkBits22to52[StackPtr] -= 0x80000000; // Limit to 31 bits StkBits53to84[StackPtr]++; // Add carry } } if (StackPtr < 4) { // If near top of stack, output 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]); sprintf(DataBuff, "%u", StkBits53to84[i]); CommaNbr(DataBuff); sprintf(CommaBuff1, "%u", StkBits22to52[i]); CommaNbr(CommaBuff1); sprintf(CommaBuff2, "%u", StkBits0to21[i]); CommaNbr(CommaBuff2); printf("StkBits53to85 = %s StkBits22to52 = %s StkBits0to21 = %s\n", DataBuff, CommaBuff1, CommaBuff2); } sprintf(DataBuff, "%u", NbrRec); CommaNbr(DataBuff); sprintf(CommaBuff1, "%u", HistFree); CommaNbr(CommaBuff1); printf("\nNbrRec(TotPos) = %s HistFree = %s\n", DataBuff, CommaBuff); puts("Overflow if HistFree > 636,000,000\n"); } } while (StackPtr1); // Repeat all combinations. // Output results. ElapsedTime = (double) clock() / CLOCKS_PER_SEC - StartTime; Bin2Dec(0); // Converts (Binary to base 10) contents at top of stack printf("\n\nResults for Start Hole = %d\n", StartHole); if (SolveForWins) { printf(" Solution Hole = %d\n", SolHole); puts("\n\nTotal possible wins:\n"); } else puts("\n\nTotal possible games:"); sprintf(DataBuff, "%u", SolE18); CommaNbr(DataBuff); sprintf(CommaBuff1, "%u", SolE9); CommaNbr(CommaBuff1); sprintf(CommaBuff2, "%u", SolE0); CommaNbr(CommaBuff2); printf(" %s E+18\n", DataBuff); printf("Plus %s E+9\n", CommaBuff1); printf("Plus %s\n\n", CommaBuff2); printf("Elapsed time = %g seconds\n", ElapsedTime); PauseMsg(); if (SolveForWins) PosCount(); // Output position counts } //************************************************************************************************* // // InitSys // //************************************************************************************************* void InitSys(void) { int i; puts(" Peg33depth"); 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; History = calloc(MAX_HISTORY + 6, 4); // Generates an array of 2 GB (+/-) // for position history HistHead = calloc(33554432, 4); // Generates an array of 2^25 elements // for history link heads puts("\nHole numbering system:\n"); puts(" 0 1 2"); puts(" 3 4 5"); puts(" 6 7 8 9 10 11 12"); puts(" 13 14 15 16 17 18 19"); puts(" 20 21 22 23 24 25 26"); puts(" 27 28 29"); puts(" 30 31 32\n"); do { puts("Enter number of hole for initial space ( 0 to 32 )"); gets(DataBuff); StartHole = atoi(DataBuff); } while ((StartHole < 0) || (StartHole > 32)); SolHole = 40; if (SolveForWins) { // If solving for number of wins do { puts("Enter number of hole for final peg ( 0 to 32 )"); gets(DataBuff); SolHole = atoi(DataBuff); } while ((SolHole < 0) || (SolHole > 32)); puts("Do you want to display any solutions?"); puts("Enter \"1\" for Yes or \"0\" for No"); gets(DataBuff); DispSolFlag = atoi(DataBuff); PegPos[SolHole] = 1; // All other holes are set to 0 by the system. GetPtrns8and25(); // High8 and Low25 bit patterns for the current // board position. HistHead[Ptrn25low] = 1; // Solution position is first record in the History[] // array. History[2] = (1 << 8) + Ptrn8high; HistFree = 3; // Next avail. array location NbrRec = 1; // One position is defined } else { // Else solve for total games DispSolFlag = 0; HistFree = 1; NbrRec = 0; } for (i = 0; i <= 32; i++) // Set up initial board PegPos[i] = 1; PegPos[StartHole] = 0; GetPtrns8and25(); // High8 and low 25 bit pattern Stk25low[1] = Ptrn25low; // Initialize stack Stk8high[1] = Ptrn8high; StkMove[1] = -1; // Setup for first move } //************************************************************************************************* // // GetPtrns8and25 // // This routine converts the occupied positions of the board's 33 holes // into two bit pattern numbers (Low25Bits and High8Bits). // //************************************************************************************************* void GetPtrns8and25(void) { unsigned Low25bits, High8bits, BitToSet; int i; High8bits = 0; Low25bits = 0; BitToSet = 1; for (i = 25; i <= 32; i++) { // Process most significant if (PegPos[i]) // bits. High8bits += BitToSet; BitToSet <<= 1; } BitToSet = 1; for (i = 0; i <= 24; i++) { // Then least sig. bits. if (PegPos[i]) Low25bits += BitToSet; BitToSet <<= 1; } Ptrn8high = High8bits; Ptrn25low = Low25bits; } //************************************************************************************************* // // ChkHist // // This routine checks the History[] array to see if the pattern represented // by "Ptrn8high", "Ptrn25low" 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 ChkHist(void) { unsigned WorkBits, 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 History[]. // Search until either a match is found or // there are no more patterns in the link list. for (RecLoc = HistHead[Ptrn25low]; RecLoc; RecLoc = History[RecLoc]) { WorkBits = History[RecLoc + 1]; // Gets value that contains the high 8 bits WorkBits &= 0xFF; // Leave just the last 8 bits. if (WorkBits == Ptrn8high) // 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 SolBits0to21, SolBits22to85. // //************************************************************************************************* void GetSol(unsigned ArrLoc) { unsigned WorkBits, HistLoc, NbrXtraElements; SolBits22to52 = 0; // Assume no extra elements. SolBits53to84 = 0; HistLoc = ArrLoc + 1; // Location for the low 22 bits WorkBits =History[HistLoc]; // Get packed data NbrXtraElements = ( WorkBits >> 30); SolBits0to21 = ((WorkBits >> 8) & 0x3FFFFF); // Get the lowest 22 bits if (NbrXtraElements) { if (NbrXtraElements == 2) // If there are more than 32 bits. SolBits53to84 = History[HistLoc + 2]; SolBits22to52 += History[HistLoc + 1]; } } //************************************************************************************************* // // Stk2Hist // // This routine creates a new record in the history arrays for the data at StackLoc. // //************************************************************************************************* void Stk2Hist(int StackLoc) { unsigned ArrLoc, LinkHead, NextLink, NbrXtraElements, MiddleBits, HighBits; MiddleBits = StkBits22to52[StackLoc]; HighBits = StkBits53to84[StackLoc]; if (HighBits) // Find out how many extra array locations NbrXtraElements = 2; // will be needed. else if (MiddleBits) NbrXtraElements = 1; else NbrXtraElements = 0; NbrRec++; // Increment nbr. records in History[] LinkHead = Stk25low[StackLoc]; // Start of L.L. for this Ptrn25low NextLink = HistHead[LinkHead]; // This goes into [ArrLoc] ArrLoc = HistFree; // New record storage starts here HistHead[LinkHead] = ArrLoc; // New record is in link list History[ArrLoc++] = NextLink; History[ArrLoc++] = (NbrXtraElements << 30) + (StkBits0to21[StackLoc] << 8) + Stk8high[StackLoc]; HistFree += 2; if (NbrXtraElements) { History[ArrLoc++] = MiddleBits; HistFree++; if (NbrXtraElements == 2) { History[ArrLoc] = HighBits; HistFree++; } } return; } //************************************************************************************************* // // PosCount // // This routine outputs the total number of positions seen and the // total number of winning positions seen. // //************************************************************************************************* void PosCount(void) { int i, TotalPos, TotalWin; // Tree search doesn't visit 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 (StkBits0to21[0] || StkBits22to52[0] || StkBits53to84[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]; sprintf(DataBuff, "%u", TotPos[i]); CommaNbr(DataBuff); sprintf(CommaBuff1, "%u", WinPos[i]); CommaNbr(CommaBuff1); printf("%5d) %15s %15s\n", i, DataBuff, CommaBuff1); } sprintf(DataBuff, "%u", TotalPos); CommaNbr(DataBuff); sprintf(CommaBuff1, "%u", TotalWin); CommaNbr(CommaBuff1); printf("Totals %15s %15s\n", DataBuff, CommaBuff1); 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 Bin0to21; unsigned Bin22to52; unsigned Bin53to84; unsigned DecE0, IncrE0; // The result in decimal will be here unsigned DecE9, IncrE9; unsigned DecE18, IncrE18; unsigned OneBil = 1000000000; int i; // Initialize for calculations DecE18 = 0; // Decimal result will be DecE9 = 0; // constructed here. DecE0 = 0; IncrE18 = 0; // Initialize increments IncrE9 = 0; IncrE0 = 1; Bin0to21 = StkBits0to21[StackPos]; for (i = 0; i <= 21; i++) { // First convert the lowest bits if (Bin0to21 & 1) // If bit exists DecE0 += IncrE0; // Increase the low total by "increment" IncrE0 += IncrE0; // Double the increment Bin0to21 >>= 1; // Move next bit into position } // Only have to work with low numbers Bin22to52 = StkBits22to52[StackPos]; for (i = 22; i <= 52; i++) { // Get the next 31 bits of the number if (Bin22to52 & 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++; } Bin22to52 >>= 1; } Bin53to84 = StkBits53to84[StackPos]; for (i = 53; i <= 84; i++) { // Get the next 32 bits of the number if (Bin53to84 & 1) { // If bit exists DecE0 += IncrE0; // Increase the low total by "increment" DecE9 += IncrE9; // Increase the middle total by increment DecE18 += IncrE18; // Increase the high 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 } if (DecE9 >= OneBil) { // Middle 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++; } Bin53to84 >>= 1; } SolE0 = DecE0; // Copy to global variables SolE9 = DecE9; SolE18 = DecE18; } //************************************************************************************************* // // 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) { int i; do { puts("\nEnter \"3\" to continue\n"); gets(DataBuff); i = atoi(DataBuff); } while( i != 3); }