Need help with recursive solution that incorporates backtracking

[sampesce]

My code is supposed to solve a game of 15 peg solitaire which is represented as an array of ones and zeros. I use a list of moves to search through the board and see what moves are able to be done. This only gets me so far though, and I eventually have to backtrack, which my program can do to a certain degree but it always gets stuck at a certain point. My current system basically will set a marker on a move that didn't work, so that it is not used again while backtracking. I then reset all of the markers once I've found a new move because some of the old moves may need to be used again. I'm really not sure how I could improve my system so that it works properly.

The board is represented as "a[15]"

The moves list is named "moves[36][5]"

The array of final moves which are to be printed out is represented as "c[13][3]"

The initial open space is hard coded to be "5" right now

The variable which holds the index for the successful moves array (c[13][3]) is "d"


Thanks for any help.




#include <iostream>


using namespace std;


void solveGame(int b[36][5]);

int chooseMove(int b[36][5]);

int pegCount();



int a[15]= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};

int c[13][3];




int d = 0;



int moveCount(int b[36][5]);



int main(){



int openSpace = 5;



a[openSpace] = 0;





int moves[36][5] = {{0, 1, 3, 0,0},
{0, 2, 5, 0,0},
{1, 3, 6, 0,0},
{1, 4, 8, 0,0},
{2, 4, 7, 0,0},
{2, 5, 9, 0,0},
{3, 6, 10, 0,0},
{3, 7, 12, 0,0},
{3, 1, 0, 0,0},
{3, 4, 5, 0,0},
{4, 7, 11, 0,0},
{4, 8, 13, 0,0},
{5, 9, 14, 0,0},
{5, 8, 12, 0,0},
{5, 2, 0, 0,0},
{5, 4, 3, 0,0},
{6, 3, 1, 0,0},
{6, 7, 8, 0,0},
{7, 4, 2, 0,0},
{7, 8, 9, 0,0},
{8, 4, 1, 0,0},
{8, 7, 6, 0,0},
{9, 5, 2, 0,0},
{9, 8, 7, 0,0},
{10, 6, 3, 0,0},
{10, 11, 12, 0,0},
{11, 7, 4, 0,0},
{11, 12, 13, 0,0},
{12, 7, 3, 0,0},
{12, 8, 5, 0,0},
{12, 11, 10, 0,0},
{12, 13, 14, 0,0},
{13, 8, 4, 0,0},
{13, 12, 11, 0,0},
{14, 9, 5, 0,0},
{14, 13, 12, 0,0}};





// calling recursive function and then printing out the moves used


solveGame(moves);


for(int i=0; i<13; i++){

cout<<c[i][0]<<" "<<c[i][1]<<" "<<c[i][2]<<endl;



}




return 0;

}

void solveGame(int b[36][5]){


int nextMove;


// base case if there is only one peg left



if(pegCount() < 2){


cout<<"solution found"<<endl<<endl;


}
else{


nextMove = chooseMove(b);



// backtracking code which undoes the previous move if there is no move that can be done




if(nextMove == 99){


a[b[c[d-1][3]][0]] = 1;

a[b[c[d-1][3]][1]] = 1;

a[b[c[d-1][3]][2]] = 0;


// this is essentially how my backtracking works, if the move has not worked, this index gets set a a '1' so that it won't be picked again on the next search
// but since this mark is reset every time a new move is found, it isn't that useful


b[c[d-1][3]][3] = 1;




c[d-1][0] = 0;

c[d-1][1] = 0;

c[d-1][2] = 0;

c[d-1][3] = 0;


d--;


}



// if there is an available move, it does the move and records it in "c"


else {


c[d][0] = b[nextMove][0];
c[d][1] = b[nextMove][1];
c[d][2] = b[nextMove][2];
c[d][3] = nextMove;



a[b[nextMove][0]] = 0;
a[b[nextMove][1]] = 0;
a[b[nextMove][2]] = 1;



d++;

}


solveGame( b);

}



}

int chooseMove(int b[36][5]){



for(int i=0; i<36;i++){




// finds the first available move that hasn't been flagged from backtracking




if(a[b[i][2]] == 0 && a[b[i][0]]==1 && a[b[i][1]]==1 && b[i][3] != 1 ){




for(int j=0; j<36; j++){

b[j][3] = 0;

}




return i;



}

}



// if no move is found, it returns 99



return 99;

}




int pegCount(){

int count = 0;

for(int i=0; i < 15; i++){

if(a[i] == 1){

count++;
}

}

return count;

}

int moveCount(int b[36][5]){


int count = 0;


for(int i=0; i<36;i++){




if(a[b[i][2]] == 0 && a[b[i][0]]==1 && a[b[i][1]]==1/* && b[i][3] != 1*/ ){


count++;


}

}



return count;



}

[mirhagk]

Here's a HUGE hint. Solve this by hand with 2 pegs, then 3, then 4, then 5, etc. Notice a nice little pattern? The game is easily solvable with a simple algorithm, needing no recursion.

On the other hand, if your teacher actually does want you do it with recursion (which they shouldn't) let me know and I can help uoi)

[sampesce]

Yes, they want me to use recursion unfortunately =/ and I'm not too familiar with it. Help would be greatly appreciated!

[mirhagk]

If you are really stuck to recursion, then I would like you to explain some aspects of your code. First of all, Peg Solitaire is a 2 dimensional board of pegs, so I would like to know why your board is a 1 dimensional array, and why your move list is 2 dimensional?

[sampesce]

Sure. Well, I didn't think how the board was represented would matter since it really came down to just flipping ones and zeroes. I made the moves list two dimensional so I would be able to group numbers to make the legal moves. Also, this board is represented as a triangle (though I don't think it matters, since all of the moves are correct for the board.)

[mirhagk]

I'm sorry I can't understand this code.

What you want to do is as follows:

Look at board and determine possible moves.
for every move discovered
do move
call this function again
undo move
end for

It kinda looks like your not using recursion in your code, you storing available moves in a list outside of the function, ideally you store that inside the function (so each call to the function has it's own list of possible moves).

In fact you wouldn't even need to keep a list of possible moves, just look for possible moves and as you find them, do the move, and call the function on itself (then undo them if the move didn't lead to a solution)

[sampesce]

Yeah my professor suggested a similar style of function, but I don't understand what you mean when you put "undo move" after you call the function. My professor had it set up the same way (I really don't have much experience with recursion, and this assignment was more of an independent one with no help)

[crossley7]

Undo a move means generally you have stored a copy of what your board looked like before you made the move and you just reset it after you have checked through.

[sampesce]

I understand what "undo move" means, I'm saying since I don't have a good knowledge of recursion, I don't get the order in which to do things. It doesn't make sense to me why undo move would come last if you had just made the move.

[crossley7]

it would be to run the simulation. It has nothing to do with the recursion really, just maintaining the position. The order to run the recursion is as mirhagk suggested is to for each potential move

1. make the move in a parallel array to the original
2. call the function you are in to check this move deeper (the recursion part)
3. reset the parallel array to your original array that you started the function with.

this will for each possibility check each possible move and so on until it reaches a point where there are no possible moves at the next level or it has reached a condition under which you have told it to exit. By the time you exit the lowest level of the function, your array will be at the original position and you should have stored whatever values you needed in either a return value or some global array/variable.

So the undo move is at the very end of your simulation so that it manages to have the same position for the next move it checks

[sampesce]

So I revised it to look differently, but it's still not working properly. Can you point out the obvious error?

where a is still the board, b is the move lost, and c is the array im trying to put the moves into. Also, I'm not sure how to format the code for this forum so that it looks normal, so I apologize for its sloppiness.



bool solvegame(int a[15], int b[36][5], int c[13][3], int moveindex){


int count = 0;

if(pegCount(a)<2){

cout<<"game over"<<endl;

for(int j = 0; j<13; j++){

cout<<c[j][0]<<" "<<c[j][1]<<" "<<c[j][2]<<endl;

}

return true;

}

for(int i =0;i<36;i++){

if(a[b[i][2]] == 0 && a[b[i][0]]==1 && a[b[i][1]]==1 ){

a[b[i][0]] = 0;
a[b[i][1]] = 0;
a[b[i][2]] = 1;

c[moveindex][0] = b[i][0];
c[moveindex][1] = b[i][1];
c[moveindex][2] = b[i][2];
count++;

for(int i=0; i < 15; i++){

cout<<a[15]<<endl;
}


solvegame(a,b,c,moveindex+1);

return true;
}
}
if(count==0){

return false;

}






}

[crossley7]

cout<<a[15]<<endl;

I think you want that to be i not 15

The rest I can't read/comprehend because of indenting issues and variable names. also, if you want to use code tage either use

[ code ][ /code ] or [ syntax="cpp" ][ /syntax ] without the spaces to get it to appear in code tags or C++ tags depending on which you want.

[mirhagk]

Have you done other recursive functions before?