# 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[0]), Integer.parseInt(toRemove[1]), 0, 0, Integer.parseInt(toRemove[2]), Integer.parseInt(toRemove[3]) };

intRemove[2] = (intRemove[0] + intRemove[4]) / 2;
intRemove[3] = (intRemove[1] + intRemove[5]) / 2;

// Undo the move
pegs[intRemove[0]][intRemove[1]] = true;
pegs[intRemove[2]][intRemove[3]] = true;
pegs[intRemove[4]][intRemove[5]] = 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[3][2];

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;
}

currentMove[0][0] = startX;
currentMove[0][1] = startY;
currentMove[1][0] = jumpX;
currentMove[1][1] = jumpY;
currentMove[2][0] = endX;
currentMove[2][1] = 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[3][3] && 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[0][0]][currentMove[0][1]] = true;
pegs[currentMove[1][0]][currentMove[1][1]] = true;
pegs[currentMove[2][0]][currentMove[2][1]] = false;

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

}

}
return false;
}
``````