//*****************************************************************************
//
// 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)