c++ recursion with arrays
- by Sam
I have this project that I'm working on for a class, and I'm not looking for the answer, but maybe just a few tips since I don't feel like I'm using true recursion. The problem involves solving the game of Hi Q or "peg solitaire" where you want the end result to be one peg remaining (it's played with a triangular board and one space is open at the start.)
I've represented the board with a simple array, each index being a spot and having a value of 1 if it has a peg, and 0 if it doesn't and also the set of valid moves with a 2 dimensional array that is 36, 3 (each move set contains 3 numbers; the peg you're moving, the peg it hops over, and the destination index.)
So my problem is that in my recursive function, I'm using a lot of iteration to determine things like which space is open (or has a value of 0) and which move to use based on which space is open by looping through the arrays. Secondly, I don't understand how you would then backtrack with recursion, in the event that an incorrect move was made and you wanted to take that move back in order to choose a different one.
This is what I have so far; the "a" array represents the board, the "b" array represents the moves, and the "c" array was my idea of a reminder as to which moves I used already. The functions used are helper functions that basically just loop through the arrays to find an empty space and corresponding move. :
void solveGame(int a[15], int b[36][3], int c[15][3]){
int empSpace;
int moveIndex;
int count = 0;
if(pegCount(a) < 2){
return;
}
else{
empSpace = findEmpty(a);
moveIndex = chooseMove( a, b, empSpace);
a[b[moveIndex][0]] = 0;
a[b[moveIndex][1]] = 0;
a[b[moveIndex][2]] = 1;
c[count][0] = b[moveIndex][0];
c[count][1] = b[moveIndex][1];
c[count][2] = b[moveIndex][2];
solveGame(a,b,c);
}
}
