/***************************************************************************** SOLVEPEG.C Solves the Windows Entertainment Pack game 'Pegged'. The internal data and solutions are 0 based while the external solutions printed are 1 based. That is, the data start in the upper left corner of the board as 0, while the output calls it 1. The program may be compiled under Borland C++, Turbo C or Microsoft C 6.0 or 5.1. Use the small memory model. By: Jeff R. Fontanesi Started: 5/20/91 Updated: 5/21/91 ******************************************************************************/ #include #include #include #include #include #include /*************** * Defines * ***************/ #define HOLES 33 // Number of holes in the board #define UP 0 // Direction up #define RT 1 // Direction right #define DN 2 // Direction down #define LT 3 // Direction left #define INTERVAL 1000 // Interval between screen updates #define TRUE 1 #define FALSE 0 /**************** * Typedefs * ****************/ typedef struct HoleTag // Hole structure { int Peg; // Contains a peg TRUE/FALSE struct HoleTag *Dir[4]; // Adjacent holes UP/RT/DN/LT } Hole; typedef struct MoveTag // List of moves structure { int FromHole; // The hole number moved from int Dir; // The direction moved } Move; /************************ * Global variables * ************************/ int iCount = 0; // Screen update interval counter int iNumPegs; // Number of pegs in board int iSolveOnce = FALSE; // Single solution flag int iSolutions = 0; // Number of solutions found Move Moves[HOLES]; // List of moves made Hole Board[HOLES]; // Array of holes for complete board char *szDirText[] = {"up","right", // Directions "down","left"}; char szName[40]; // Name of puzzle char szBusyChars[] = "/-\\|"; // Characters for rotating busy bar int iBusyIndex = 0; // Index for above array /*************************** * Function prototypes * ***************************/ void Solve(int Level); void PickPuzzle(int ch); void InitPuzzle(int iPegCount, int iPegNums, ...); void Title(void); void Help(void); /************ * MAIN * ************/ void main(int argc, char *argv[]) { if (argc < 2 || strchr(argv[1],'?')) // If ? on cmd line Help(); // Show help and quit if (argv[2][1] == '1') // If /1 on cmd line iSolveOnce = TRUE; // Set single solution flag PickPuzzle(argv[1][1]); // Pick which puzzle to solve Solve(0); // Solve the puzzle recursively printf("There are %d solutions to the %s puzzle.\n",iSolutions,szName); } /**************************************************************************** Function: Solve Description: Solves the puzzle. See algorythm below. This routine shows a rotating bar to show the user something's happening. It does this by cycling through the characters in szBusyChars. This happens every INTERVAL calls to the function so we don't spend too much time updating the screen. Parameters: int iNumMoves The number of moves that have been made so far. Returns: None Globals read: iCount, szBusyChars, iBusyIndex, iNumPegs, iSolveOnce iSolutions, szDirText, Moves, Board written: iCount, iBusyIndex, iSolutions, Moves, Board Calls: (itself) Called by: main Programmers: JRF Updated: 5/21/91 Algorythm: For all the holes in the board If all moves made Print list of moves return For all directions (UP/RT/DN/LT) If current hole has a peg and the hole in direction exists and has a peg and the hole beyond the hole in direction exists and is empty Jump and record move Recurse Undo jump ****************************************************************************/ void Solve(int iNumMoves) { int iHole, iDir, i; if (++iCount > INTERVAL) // If up to INTERVAL { iCount = 0; // Reset counter if (!szBusyChars[iBusyIndex]) // If end of busy char's iBusyIndex = 0; // Reset index cprintf("%c\r",szBusyChars[iBusyIndex++]); // Show rotating busy bar kbhit(); // Allow Ctrl-Break } for (iHole = 0; iHole < HOLES; iHole++) // For all holes in board { if (iNumMoves == iNumPegs-1) // If all moves made { printf("Solution %d:\n",++iSolutions); // Show solution number for (i = 0; i < iNumMoves; i++) // Show list of moves printf("%2d. Move %-2d %s\n",i+1, Moves[i].FromHole+1,szDirText[Moves[i].Dir]); printf("\n"); if (iSolveOnce) // If /1 on cmd line exit(0); // Quit return; } for (iDir = 0; iDir < 4; iDir++) // For all directions { if (Board[iHole].Peg && // If there's a peg Board[iHole].Dir[iDir] && // and an adjacent hole Board[iHole].Dir[iDir]->Peg && // with a peg Board[iHole].Dir[iDir]->Dir[iDir] && // and a further hole !Board[iHole].Dir[iDir]->Dir[iDir]->Peg)// without a peg { Board[iHole].Peg = FALSE; // Lift peg Board[iHole].Dir[iDir]->Peg = FALSE; // Remove jumped peg Board[iHole].Dir[iDir]->Dir[iDir]->Peg // Place peg = TRUE; Moves[iNumMoves].FromHole = iHole; // Save hole moved from Moves[iNumMoves].Dir = iDir; // Save direction Solve(iNumMoves+1); // Recurse Board[iHole].Peg = TRUE; // Put peg back Board[iHole].Dir[iDir]->Peg = TRUE; // Put jumped peg back Board[iHole].Dir[iDir]->Dir[iDir]->Peg // Remove jumping peg = FALSE; } } } } /**************************************************************************** Function: PickPuzzle Description: Picks which puzzle to solve. Parameters: int ch The character specified on the command line representing the puzzle to be solved. Returns: None Globals read: None written: szName, iNumPegs Calls: Title, Help Called by: main Programmers: JRF Updated: 5/20/91 ****************************************************************************/ void PickPuzzle(int ch) { switch (toupper(ch)) { case 'C': strcpy(szName,"Cross"); iNumPegs = 6; InitPuzzle(iNumPegs, 4, 8, 9, 10, 16, 23 ); break; case 'P': strcpy(szName,"Plus"); iNumPegs = 9; InitPuzzle(iNumPegs, 4, 9, 14, 15, 16, 17, 18, 23, 24 ); break; case 'F': strcpy(szName,"Fireplace"); iNumPegs = 11; InitPuzzle(iNumPegs, 0, 1, 2, 3, 4, 5, 8, 9, 10, 15, 17); break; case 'A': strcpy(szName,"Up Arrow"); iNumPegs = 17; InitPuzzle(iNumPegs, 1, 3, 4, 5, 7, 8, 9, 10, 11, 16, 23, 27, 28, 29, 30, 31, 32); break; case 'Y': strcpy(szName,"Pyramid"); iNumPegs = 16; InitPuzzle(iNumPegs, 4, 8, 9, 10, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26); break; case 'D': strcpy(szName,"Diamond"); iNumPegs = 24; InitPuzzle(iNumPegs, 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 17, 18, 19, 21, 22, 23, 24, 25, 27, 28, 29, 31); break; case 'S': strcpy(szName,"Solitaire"); iNumPegs = 32; InitPuzzle(iNumPegs, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32); break; default: Help(); } Title(); printf("Solving the %s puzzle...\n\n",szName); } /**************************************************************************** Function: InitPuzzle Description: Initializes the board Parameters: int iPegCount The number of pegs in the puzzle. int iPegNums, ... List of pegs to be placed in holes. Returns: None Globals read: None written: Board Calls: None Called by: PickPuzzle Programmers: JRF Updated: 5/20/91 ****************************************************************************/ void InitPuzzle(int iPegCount, int iPegNums, ...) { int i; va_list marker; for (i = 0; i < HOLES; i++) // Clear all pegs Board[i].Peg = FALSE; Board[iPegNums].Peg = TRUE; // Place first peg va_start(marker, iPegNums); for (i = 1; i < iPegCount; i++) // Place rest of pegs Board[va_arg(marker,int)].Peg = TRUE; va_end(marker); Board[0].Dir[0] = NULL; // Initialize board pointers Board[0].Dir[1] = &Board[1]; // The board looks like this: Board[0].Dir[2] = &Board[3]; Board[0].Dir[3] = NULL; // 00 01 02 // 03 04 05 Board[1].Dir[0] = NULL; // 06 07 08 09 10 11 12 Board[1].Dir[1] = &Board[2]; // 13 14 15 16 17 18 19 Board[1].Dir[2] = &Board[4]; // 20 21 22 23 24 25 26 Board[1].Dir[3] = &Board[0]; // 27 28 29 // 30 31 32 Board[2].Dir[0] = NULL; Board[2].Dir[1] = NULL; Board[2].Dir[2] = &Board[5]; Board[2].Dir[3] = &Board[1]; Board[3].Dir[0] = &Board[0]; Board[3].Dir[1] = &Board[4]; Board[3].Dir[2] = &Board[8]; Board[3].Dir[3] = NULL; Board[4].Dir[0] = &Board[1]; Board[4].Dir[1] = &Board[5]; Board[4].Dir[2] = &Board[9]; Board[4].Dir[3] = &Board[3]; Board[5].Dir[0] = &Board[2]; Board[5].Dir[1] = NULL; Board[5].Dir[2] = &Board[10]; Board[5].Dir[3] = &Board[4]; Board[6].Dir[0] = NULL; Board[6].Dir[1] = &Board[7]; Board[6].Dir[2] = &Board[13]; Board[6].Dir[3] = NULL; Board[7].Dir[0] = NULL; Board[7].Dir[1] = &Board[8]; Board[7].Dir[2] = &Board[14]; Board[7].Dir[3] = &Board[6]; Board[8].Dir[0] = &Board[3]; Board[8].Dir[1] = &Board[9]; Board[8].Dir[2] = &Board[15]; Board[8].Dir[3] = &Board[7]; Board[9].Dir[0] = &Board[4]; Board[9].Dir[1] = &Board[10]; Board[9].Dir[2] = &Board[16]; Board[9].Dir[3] = &Board[8]; Board[10].Dir[0] = &Board[5]; Board[10].Dir[1] = &Board[11]; Board[10].Dir[2] = &Board[17]; Board[10].Dir[3] = &Board[9]; Board[11].Dir[0] = NULL; Board[11].Dir[1] = &Board[12]; Board[11].Dir[2] = &Board[18]; Board[11].Dir[3] = &Board[10]; Board[12].Dir[0] = NULL; Board[12].Dir[1] = NULL; Board[12].Dir[2] = &Board[19]; Board[12].Dir[3] = &Board[11]; Board[13].Dir[0] = &Board[6]; Board[13].Dir[1] = &Board[14]; Board[13].Dir[2] = &Board[20]; Board[13].Dir[3] = NULL; Board[14].Dir[0] = &Board[7]; Board[14].Dir[1] = &Board[15]; Board[14].Dir[2] = &Board[21]; Board[14].Dir[3] = &Board[13]; Board[15].Dir[0] = &Board[8]; Board[15].Dir[1] = &Board[16]; Board[15].Dir[2] = &Board[22]; Board[15].Dir[3] = &Board[14]; Board[16].Dir[0] = &Board[9]; Board[16].Dir[1] = &Board[17]; Board[16].Dir[2] = &Board[23]; Board[16].Dir[3] = &Board[15]; Board[17].Dir[0] = &Board[10]; Board[17].Dir[1] = &Board[18]; Board[17].Dir[2] = &Board[24]; Board[17].Dir[3] = &Board[16]; Board[18].Dir[0] = &Board[11]; Board[18].Dir[1] = &Board[19]; Board[18].Dir[2] = &Board[25]; Board[18].Dir[3] = &Board[17]; Board[19].Dir[0] = &Board[12]; Board[19].Dir[1] = NULL; Board[19].Dir[2] = &Board[26]; Board[19].Dir[3] = &Board[18]; Board[20].Dir[0] = &Board[13]; Board[20].Dir[1] = &Board[21]; Board[20].Dir[2] = NULL; Board[20].Dir[3] = NULL; Board[21].Dir[0] = &Board[14]; Board[21].Dir[1] = &Board[22]; Board[21].Dir[2] = NULL; Board[21].Dir[3] = &Board[20]; Board[22].Dir[0] = &Board[15]; Board[22].Dir[1] = &Board[23]; Board[22].Dir[2] = &Board[27]; Board[22].Dir[3] = &Board[21]; Board[23].Dir[0] = &Board[16]; Board[23].Dir[1] = &Board[24]; Board[23].Dir[2] = &Board[28]; Board[23].Dir[3] = &Board[22]; Board[24].Dir[0] = &Board[17]; Board[24].Dir[1] = &Board[25]; Board[24].Dir[2] = &Board[29]; Board[24].Dir[3] = &Board[23]; Board[25].Dir[0] = &Board[18]; Board[25].Dir[1] = &Board[26]; Board[25].Dir[2] = NULL; Board[25].Dir[3] = &Board[24]; Board[26].Dir[0] = &Board[19]; Board[26].Dir[1] = NULL; Board[26].Dir[2] = NULL; Board[26].Dir[3] = &Board[25]; Board[27].Dir[0] = &Board[22]; Board[27].Dir[1] = &Board[28]; Board[27].Dir[2] = &Board[30]; Board[27].Dir[3] = NULL; Board[28].Dir[0] = &Board[23]; Board[28].Dir[1] = &Board[29]; Board[28].Dir[2] = &Board[31]; Board[28].Dir[3] = &Board[27]; Board[29].Dir[0] = &Board[24]; Board[29].Dir[1] = NULL; Board[29].Dir[2] = &Board[32]; Board[29].Dir[3] = &Board[28]; Board[30].Dir[0] = &Board[27]; Board[30].Dir[1] = &Board[31]; Board[30].Dir[2] = NULL; Board[30].Dir[3] = NULL; Board[31].Dir[0] = &Board[28]; Board[31].Dir[1] = &Board[32]; Board[31].Dir[2] = NULL; Board[31].Dir[3] = &Board[30]; Board[32].Dir[0] = &Board[29]; Board[32].Dir[1] = NULL; Board[32].Dir[2] = NULL; Board[32].Dir[3] = &Board[31]; } /**************************************************************************** Function: Title Description: Shows the title of the program Parameters: None Returns: None Globals read: None written: None Calls: None Called by: PickPuzzle, Help Programmers: JRF Updated: 5/21/91 ****************************************************************************/ void Title(void) { printf("SOLVEPEG - Finds all solutions to the Windows Entertainment Pack Game \"Pegged\"\n" " Jeff R. Fontanesi - 5/21/91\n" "\n"); } /**************************************************************************** Function: Help Description: Shows command line arguments Parameters: None Returns: None Globals read: None written: None Calls: None Called by: main, PickPuzzle Programmers: JRF Updated: 5/20/91 ****************************************************************************/ void Help(void) { Title(); printf("SOLVEPEG [/C][/P][/F][/A][/Y][/D][/S] [/1]\n" "\n" " /C Cross\n" " /P Plus\n" " /F Fireplace\n" " /A Up Arrow\n" " /Y Pyramid\n" " /D Diamond\n" " /S Solitaire\n" "\n" " /1 Stop after one solution found.\n" "\n"); exit(0); }