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.

Owner

losvedir 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.

Owner

losvedir 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