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