Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Cracker Barrel Triangle Peg Jumping Game Solver
/* Solves one of those triangle shaped peg jumping puzzles.
You begin with a board composed of n rows, where the i-th
row contains i columns. e.g.:
X
X X
X X X
The board begins with pegs in all holes but one. A peg can
jump over another peg if it can land in a hole on the other
side. The jumped peg is removed. The goal is to finish with
a single peg remaining.
*/
#include<stdio.h>
#include<stdlib.h>
#define PUZZROWS 5 // Number of rows in the puzzle
#define PEGS (PUZZROWS * (PUZZROWS + 1)) / 2 // Number of pegs in the puzzle
typedef struct board {
int peg[PEGS]; // each board will represent its pegs by an array of integers
int *row[PUZZROWS]; // these rows will point at the peg array
int lastMove; // move type (0-5) to get from parent position to this one
int pegrow, pegcol; // row and column of peg that jumped to get to this position
struct board *previousPosition; //the board layout prior to this one
} Board;
typedef struct boardnode { // Search will be depth-first, using a list of Nodes
Board *board;
struct boardnode *next;
} Node;
// Maybe shouldn't be globally declared, but helpful for debugging errors
// in all functions, so I'll just declare them once here and be done with it
void printBoardList(Board*); // prints a board and all its ancestors
void printBoard(Board *layout);
void printList(Node *node);
int totalpossibilities=0; // number of boards generated during search, just out of curiosity
// Begins with a start position and adds it to the search queue. Then, it loops:
// Is first element of queue a winning position (has only one peg)? If so, break --
// solution found; if not, remove it, generate all boards that can be formed by
// any single legal jump, and add them to the queue.
main() {
int winningPosition(Board *b);
void removeFirstAndEnqueuePossibleMoves(Node **queue, Node **visited);
Board *reverseBoardOrder(Board*);
Board *newBoardFromIntArray(int arrayOfBoardLayout[]);
void cleanUp(Node *list);
Node *queue; //List of to-be-examined nodes, "queue" points to the first one
Node *visited; // list of examined nodes, for memory clean-up at end
int startboard[] = {
0,
1, 1,
1, 1, 1,
1, 1, 1, 1,
1, 1, 1, 1, 1,
};
int i;
Board *first, *solution;
first = newBoardFromIntArray(startboard);
first->previousPosition = NULL;
queue = (Node *) malloc(sizeof(Node));
queue->board = first;
queue->next = NULL;
visited = (Node *) malloc(sizeof(Node));
visited->board = NULL;
visited->next = NULL;
totalpossibilities+=2;
while( queue != NULL ) {
if (winningPosition(queue->board))
break;
removeFirstAndEnqueuePossibleMoves(&queue, &visited);
}
if (!queue) {
printf("No solution found.\n");
printf("Boards generated: %d\n", totalpossibilities);
} else {
printf("Starting board:\n");
printBoard(first);
printf("Solution:\n");
solution = reverseBoardOrder(queue->board);
printBoardList(solution);
printf("Boards generated: %d\n", totalpossibilities);
}
cleanUp(visited);
cleanUp(queue);
return 0;
}
void removeFirstAndEnqueuePossibleMoves(Node **q, Node **v) {
void addBoardToFrontOfList(Board*, Node **);
// These functions each check if a given peg on a given board can
// make a certain type of jump. They return a pointer to the resulting board
// if so, and NULL otherwise. (These malloc memory and return the ptr):
Board *boardFromJumpUpAndLeft(Board*, int row, int col);
Board *boardFromJumpUpAndRight(Board*, int row, int col);
Board *boardFromJumpLeft(Board*, int row, int col);
Board *boardFromJumpRight(Board*, int row, int col);
Board *boardFromJumpDownAndLeft(Board*, int row, int col);
Board *boardFromJumpDownAndRight(Board*, int row, int col);
// An array of pointers to the above functions:
Board *(*boardJumpFunction[])(Board*,int,int) = {boardFromJumpUpAndLeft, boardFromJumpUpAndRight, boardFromJumpLeft, boardFromJumpRight, boardFromJumpDownAndLeft, boardFromJumpDownAndRight};
int r, c, f;
Board *parentBoard, *newBoard;
Node *newNodeList = NULL; // This will be a list of the generated boards
Node *oldq, *oldv;
parentBoard = (*q)->board;
// Generate new possible boards, and add to newNodeList
for(r=0; r<PUZZROWS; r++) { // for each row:
for(c=0; c<r+1; c++) { // for each column in a row:
if (*(parentBoard->row[r]+c) == 1) { // If this space has a peg
for(f=0; f<6; f++) { // Try all 6 possible jumps
if (newBoard = (*boardJumpFunction[f])(parentBoard, r, c)) {
addBoardToFrontOfList(newBoard, &newNodeList);
}
}
}
}
}
// Add generated newNodeList to front of queue, and add the now-examined
// board to the visited list
oldv = *v;
oldq = *q;
// Add newNodeList to front of queue
if (newNodeList) {
*q = newNodeList;
while (newNodeList->next) // Get to end of list
newNodeList = newNodeList->next;
newNodeList->next = oldq->next;
} else {
*q = (*q)->next;
}
// Add q to the front of the visited list
*v = oldq;
oldq->next = oldv;
}
// Helper function for all the "boardFromJumpXXX" functions.
// Takes a board pointer, the row/col of peg in question,
// and the offset -- r and c -- describing how the peg jumps.
// r and c can be -2, 0, or 2. (e.g. JumpUpAndLeft has r=-2, c=-2)
Board *jumpHelperFunction(Board *parent, int row, int col, int r, int c) {
Board *newBoard = NULL;
Board *copyBoard(Board *);
if ( row+r >= 0 // landing row is not off the top of puzzle?
&& row+r < PUZZROWS // landing row is not off bottom of puzzle?
&& col+c >= 0 // landing column is not off left side of puzzle?
&& col+c <= row+r // landing column is not off right? (# col's in row == row #)
&& *(parent->row[row+r] + (col+c)) == 0 // landing space is empty
&& *(parent->row[row+(r/2)] + (col+(c/2))) == 1 // there's a peg to jump
) {
newBoard = copyBoard(parent);
newBoard->previousPosition = parent;
newBoard->pegrow = row;
newBoard->pegcol = col;
*(newBoard->row[row+r] + (col+c)) = 1; // landing space is filled in
*(newBoard->row[row+(r/2)] + (col+(c/2))) = 0; // jumped peg is removed
*(newBoard->row[row] + col) = 0; // jumped-from space is now empty
return newBoard;
} else {
return NULL; // Not a valid move
}
}
// e.g. 0 1
// 0 1 -> 0 0
// 0 0 1 0 0 0
Board *boardFromJumpUpAndLeft(Board *parent, int row, int col) {
Board *newBoard = NULL;
newBoard = jumpHelperFunction(parent, row, col, -2, -2);
if (newBoard)
newBoard->lastMove=0;
return newBoard;
}
// e.g. 0 1
// 1 0 -> 0 0
// 1 0 0 0 0 0
Board *boardFromJumpUpAndRight(Board *parent, int row, int col) {
Board *newBoard = NULL;
newBoard = jumpHelperFunction(parent, row, col, -2, 0);
if (newBoard)
newBoard->lastMove=1;
return newBoard;
}
// e.g. 0 0
// 0 0 -> 0 0
// 0 1 1 1 0 0
Board *boardFromJumpLeft(Board *parent, int row, int col) {
Board *newBoard = NULL;
newBoard = jumpHelperFunction(parent, row, col, 0, -2);
if (newBoard)
newBoard->lastMove=2;
return newBoard;
}
// e.g. 0 0
// 0 0 -> 0 0
// 1 1 0 0 0 1
Board *boardFromJumpRight(Board *parent, int row, int col) {
Board *newBoard = NULL;
newBoard = jumpHelperFunction(parent, row, col, 0, 2);
if (newBoard)
newBoard->lastMove=3;
return newBoard;
}
// e.g. 1 0
// 1 0 -> 0 0
// 0 0 0 1 0 0
// Note: Because array layout is right triangle, "down and left"
// is really straight down (maintains same column).
Board *boardFromJumpDownAndLeft(Board *parent, int row, int col) {
Board *newBoard = NULL;
newBoard = jumpHelperFunction(parent, row, col, 2, 0);
if (newBoard)
newBoard->lastMove=4;
return newBoard;
}
// e.g. 1 0
// 0 1 -> 0 0
// 0 0 0 0 0 1
Board *boardFromJumpDownAndRight(Board *parent, int row, int col) {
Board *newBoard = NULL;
newBoard = jumpHelperFunction(parent, row, col, 2, 2);
if (newBoard)
newBoard->lastMove=5;
return newBoard;
}
Board *copyBoard(Board *oldBoard) {
Board *newBoard;
int i, triangleNumberOffset;
if (newBoard = (Board*) malloc(sizeof(Board)) ){
for(i=0; i<PEGS; i++) {
newBoard->peg[i] = oldBoard->peg[i];
}
for(i=0, triangleNumberOffset=0; i<PUZZROWS; i++) {
newBoard->row[i] = newBoard->peg + triangleNumberOffset;
triangleNumberOffset += (i+1);
}
return newBoard;
} else {
return NULL;
}
}
void addBoardToFrontOfList(Board *brd, Node **first) {
Node *newNode;
newNode = (Node*) malloc(sizeof(Node));
totalpossibilities++;
newNode->board = brd;
newNode->next = *first;
*first = newNode;
}
int winningPosition(Board *b) {
int i, pegcount=0;
for (i=0; i<PEGS; i++) {
if (b->peg[i] == 1)
pegcount++;
}
return (pegcount == 1);
}
Board *newBoardFromIntArray(int boardAsIntArray[]) {
Board *newBoard=NULL;
int i, triangleNumberOffset;
if(newBoard = (Board*) malloc(sizeof(Board))) {
for(i=0; i<PEGS; i++) {
newBoard->peg[i] = boardAsIntArray[i];
}
for(i=0, triangleNumberOffset=0; i<PUZZROWS; i++) {
newBoard->row[i] = newBoard->peg + triangleNumberOffset;
triangleNumberOffset += (i+1);
}
}
return newBoard;
}
void intArrayToBoard(int boardAsIntArray[], Board *boardAsStruct) {
int i, triangleNumberOffset;
for(i=0; i<PEGS; i++) {
boardAsStruct->peg[i] = boardAsIntArray[i];
}
for(i=0, triangleNumberOffset=0; i<PUZZROWS; i++) {
boardAsStruct->row[i] = boardAsStruct->peg + triangleNumberOffset;
triangleNumberOffset += (i+1);
}
}
void printBoard(Board *boardLayout) {
int i, j, k;
for(i=0; i<PUZZROWS; i++){
for(k=0; k<(PUZZROWS-1)-i; k++) { // white space to center rows
printf(" ");
}
for(j=0; j<i+1; j++) {
printf("%d ",*((boardLayout->row[i])+j));
}
printf("\n");
}
printf("By jumping peg (row:%d, col:%d) ",boardLayout->pegrow +1, boardLayout->pegcol +1);
switch (boardLayout->lastMove) {
case 0:
printf("up and left\n\n");
break;
case 1:
printf("up and right\n\n");
break;
case 2:
printf("straight left\n\n");
break;
case 3:
printf("straight right\n\n");
break;
case 4:
printf("down and left\n\n");
break;
case 5:
printf("down and right\n\n");
break;
}
}
void printList(Node *node) {
while (node) {
printBoard(node->board);
node = node->next;
}
}
// Takes a Board* and reverses the chain of "previousPosition"s, returns the new first
Board *reverseBoardOrder(Board *first) {
Board *child, *parent;
for(child=NULL; first->previousPosition; first = parent) {
parent = first->previousPosition;
first->previousPosition = child;
child = first;
}
first->previousPosition = child;
return first;
}
void printBoardList(Board *first) {
while (first) {
printBoard(first);
first = first->previousPosition;
}
}
void cleanUp(Node *l) {
Node *next;
int i=0;
for ( ; l; l = next) {
next = l->next;
free(l->board);
free(l);
i++;
}
printf("freed %d\n",i);
}
//;;;;;;;;;; Testing portion ;;;;;;;;;;
/* Board *testBoard; */
/* Node *testNode; */
/* printf("Testing intArrayToBoard and printBoard:\n"); */
/* // Initialize starting position, and linked list */
/* intArrayToBoard(startboard, &first); */
/* first.previousPosition = NULL; */
/* printBoard(&first); */
/* printf("Testing boardFromJumpUpAndLeft:\n"); */
/* testBoard = boardFromJumpUpAndLeft(&first, 2, 2); */
/* printBoard(testBoard); */
/* printf("Testing Queue. Expect same board as first\n"); */
/* queue = (Node *) malloc(sizeof(Node)); */
/* queue->board = &first; */
/* queue->next = NULL; */
/* printBoard(queue->board); */
/* printf("Testing printList:\n"); */
/* testNode = malloc(sizeof(Node)); */
/* testNode->board = testBoard; */
/* testNode->next = queue; */
/* printList(testNode); */
/* printf("Testing removeFirstAndEnqueuePossibleMoves:\n"); */
/* removeFirstAndEnqueuePossibleMoves(&queue); */
/* printList(queue); */
//;;;;;;;;;; End testing ;;;;;;;;;;
@losvedir

This comment has been minimized.

Copy link
Owner Author

commented Nov 3, 2010

Initial import -- works, but ugly. Would like to refactor parts.

Also, I don't keep track of my malloc's to free later....

@losvedir

This comment has been minimized.

Copy link
Owner Author

commented Nov 7, 2010

Okay, neatened up a bit -- commented a little better, refactored, and I free all my malloc'ed memory now...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.