-----------------------------------

sampesce

Sun Feb 12, 2012 9:03 pm


Need help with recursive solution that incorporates backtracking

-----------------------------------

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 


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