Cracker Barrel Triangle Peg Jumping Game Solver

gistfile1.c

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