# Recursive backtracking for a game solution - adding / removing the moves made in a string

This is an assignment for my school. The premise of the assignment is to make a working solution to solve Peg Solitaire boards (which is a board game). Our task is to return a string of the moves made. I basically have the solution done, but I have had a little help with it and I'm asking here to make sure I fully understand the working of the code.

I made a simpler version of the string concatenation add / remove, and it seems to not be working properly. I'm wondering if anyone here is able to enlighten me to my error.

The code that I have found works most effectively is

``````String[] toRemove = (move.get(move.size() -1 )).split(" ");
int[] intRemove = {Integer.parseInt(toRemove), Integer.parseInt(toRemove), 0, 0, Integer.parseInt(toRemove), Integer.parseInt(toRemove) };

intRemove = (intRemove + intRemove) / 2;
intRemove = (intRemove + intRemove) / 2;

// Undo the move
pegs[intRemove][intRemove] = true;
pegs[intRemove][intRemove] = true;
pegs[intRemove][intRemove] = false;
``````

I tried another version which stores the moves made into an array instead of grabbing it from the ArrayList string, but it doesn't seem to be giving me a full solution on the boards with more pegs.

``````public class PegSolitaire {

// ArrayList which will be what we return as the list of moves
public static ArrayList<String> move = new ArrayList<>();

// ArrayList to store temporary moves in case of undo
public static int[][] currentMove = new int;

private static boolean tryMove(boolean[][] pegs, int startX, int startY, int jumpX, int jumpY, int endX, int endY ) {

// Are we starting or ending on one of the 4 corners?
if ((startX < 2|| startX > 4) && (startY < 2 || startY > 4)
|| (jumpX < 2 || jumpX > 4) && (jumpY < 2 || jumpY > 4)
|| (endX < 2  || endX > 4) && (endY < 2 || endY > 4) ) {
return false;
}

// Are we starting or ending outside the bounds?
if(startX < 0   || startY < 0 || startX >= pegs.length || startY >= pegs.length
|| jumpX < 0 || jumpY < 0  || jumpX >= pegs.length  || jumpY >= pegs.length
|| endX < 0  || endY < 0   || endX >= pegs.length   || endY >= pegs.length) {
return false;
}

// Are we attempting to step over an empty space?
if (!pegs[jumpX][jumpY]) {
return false;
}

// Are we attempting to step onto a peg?
if (pegs[endX][endY]) {
return false;
}

// Are we attempting to move a spot without a peg?
if (!pegs[startX][startY]) {
return false;
}

// Store the move made
currentMove = startX;
currentMove = startY;
currentMove = jumpX;
currentMove = jumpY;
currentMove = endX;
currentMove = endY;

// All check out, make the move
pegs[startX][startY] = false;
pegs[jumpX][jumpY] = false;
pegs[endX][endY] = true;
// Add the move into the ArrayList
move.add( startX + " " + startY + " " + endX + " " + endY );
return true;
}

// Count how many remaining pegs are on the board
public static int pegCount(boolean[][] pegs) {
int count = 0;

for (int i = 0; i < pegs.length; i++) {
for (int j = 0; j < pegs.length; j++) {
if(pegs[i][j]) count = count + 1;
}
}

return count;
}

public static boolean nextPeg(boolean[][] pegs) {

// Check if we're finished with the game yet
if(pegs && pegCount(pegs) == 1) return true;

for(int i = 0; i < pegs.length; i++) {
for(int j = 0; j < pegs.length; j++) {
if (tryMove(pegs, i, j, i + 1 ,j ,i + 2, j) ||
tryMove(pegs, i, j, i - 1 ,j ,i - 2, j) ||
tryMove(pegs, i, j, i ,j - 1 ,i, j - 2) ||
tryMove(pegs, i, j, i ,j + 1 ,i, j + 2)) {

if(nextPeg(pegs)) {
return true;
}

// Undo the move
pegs[currentMove][currentMove] = true;
pegs[currentMove][currentMove] = true;
pegs[currentMove][currentMove] = false;

move.remove(move.size() - 1);
}

}

}
return false;
}
``````