Solves the Cracker Barrell peg game.

peggame.cpp

#include <iostream>
#include <vector>
 
const int HOLES = 15;
const int MOVES = 18;
const int JUMP = 3;
 
bool play(int pegs[], int board[][JUMP], int remaining, std::vector<int>& moves) {
 
    if (remaining == 1) {
        return true;
    }
 
    for (int i = 0; i < MOVES; i++) {
        if (pegs[board[i][0]] == 1 && pegs[board[i][1]] == 1 && pegs[board[i][2]] == 0) {
            pegs[board[i][0]] = 0;
            pegs[board[i][1]] = 0;
            pegs[board[i][2]] = 1;
 
            bool success = play(pegs, board, remaining-1, moves);
            if (success) {
                moves.push_back(board[i][2]);
                moves.push_back(board[i][0]);
                return true;
            }
 
            pegs[board[i][0]] = 1;
            pegs[board[i][1]] = 1;
            pegs[board[i][2]] = 0;
        }
 
        if (pegs[board[i][0]] == 0 && pegs[board[i][1]] == 1 && pegs[board[i][2]] == 1) {
            pegs[board[i][0]] = 1;
            pegs[board[i][1]] = 0;
            pegs[board[i][2]] = 0;
 
            bool success = play(pegs, board, remaining-1, moves);
            if (success) {
                moves.push_back(board[i][0]);
                moves.push_back(board[i][2]);
                return true;
            }
 
            pegs[board[i][0]] = 0;
            pegs[board[i][1]] = 1;
            pegs[board[i][2]] = 1;
        }
    }
 
    return false;
}
 
int main() {
 
    int open;
    int pegs[HOLES];
    int board[MOVES][JUMP] =
      {{0,1,3},
       {0,2,5},
       {1,3,6},
       {1,4,8},
       {2,4,7},
       {2,5,9},
       {3,4,5},
       {3,6,10},
       {3,7,12},
       {4,7,11},
       {4,8,15},
       {5,8,12},
       {5,9,14},
       {6,7,8},
       {7,8,9},
       {10,11,12},
       {11,12,13},
       {12,13,14}};
    std::vector<int> moves;
    std::cout << "Enter a value from 0 to 14 representing the open space: ";
    std::cin >> open;
 
    for (int i = 0; i < HOLES; i++) {
        if (i == open) {
            pegs[i] = 0;
        }
        else {
            pegs[i] = 1;
        }
    }
 
    play(pegs, board, HOLES-1, moves);
    for (int i = moves.size()-2; i >= 0; i -= 2) {
        std::cout << "Jump from peg hole " << moves[i+1] << " to peg hole " << moves[i] << "." << std::endl;
    }
 
    return 0;
}