Created
November 3, 2010 19:33
-
-
Save losvedir/661564 to your computer and use it in GitHub Desktop.
Cracker Barrel Triangle Peg Jumping Game Solver
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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 ;;;;;;;;;; |
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
Initial import -- works, but ugly. Would like to refactor parts.
Also, I don't keep track of my malloc's to free later....