# Peg solitaire solution program

I am writing an assignment in java for my data structures course. It is to find a solution to a peg solitaire board by using backtracking recursion. I thought I have a good solution in the works through saving the states of the board in stacks and then popping the board back when I need to go backwards. The problem I can't figure out is why my board I pop off the stack when I start backtracking is is my current game board and not what I pushed onto my stack. I feel I have implemented the stack wrong somehow but I am not sure where I went wrong. I know there are other problems with he code for me to iron out still but not being able to backtrack my board is really holding me up. If anyone can provide insight I would appreciate it. My two classes are currently as follows.

``````public class Board {
private char[][] board = new char[7][7];

public Board() {
for(int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
if (i == 3 && j == 3) {
board[i][j] = 'O';
} else if (i == 0 && j == 0 || i == 1 && j == 0 || i == 0 && j == 1 || i == 1 && j == 1
|| i == 0 && j == 5 || i == 1 && j == 5 || i == 0 && j == 6 || i == 1 && j == 6
|| i == 5 && j == 0 || i == 5 && j == 1 || i == 6 && j == 0 || i == 6 && j == 1
|| i == 5 && j == 5 || i == 6 && j == 6 || i == 5 && j == 6 || i == 6 && j == 5) {
board[i][j] = ' ';
} else {
board[i][j] = 'X';
}
}
}
}

public void setElement(char n, int x, int y) {
board[x][y] = n;
}

public char getElement(int x, int y ) {
return board[x][y];
}

}

import java.util.Stack;

public class Puzzle {

private static int pegs;
private static int[] move = new int [3];
static Stack<Integer> xStack = new Stack();
static Stack<Integer> yStack = new Stack();
static Stack<Integer> directionStack = new Stack();
static Stack<Board> boardState = new Stack();

public static void main(String[]args) {
Board board = new Board();
print(board);
move[0] = 0;
move[1] = 0;
move[2] = 0;
findSolution(move, board);
}

public static void print(Board board) {
for(int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(board.getElement(i, j));
}
System.out.println();
}
}

public static void findSolution(int[] move, Board board) {

if (pegs == 1 && board.getElement(3,3) == 'X') { //correct solution
System.out.println("Solution found!");
print(board);
return;
} else if (pegs == 1 && board.getElement(3,3) != 'X') { //incorrect solution
move[0] = (int) xStack.pop();
move[1] = (int) yStack.pop();
move[2] = (int) directionStack.pop();
undo(board);
boardState.pop();
pegs++;
findSolution(move, board);
}

move = findMove(move, board);

if (move[0] == 0 && move[1] == 0) {      //no moves then backtrack
move[0] = (int) xStack.pop();
move[1] = (int) yStack.pop();
move[2] = (int) directionStack.pop();
boardState.pop();
undo(board);
pegs++;
findSolution(move, board);
}

xStack.push(move[0]);
yStack.push(move[1]);
directionStack.push(move[2]); // push moves onto stack
boardState.push(board);     //push board onto board stack
makeMove(move, board);    //change the board
move[0] = 0;
move[1] = 0;
move[2] = 0;          //reset move
System.out.println();
print(board);
findSolution(move, board);
}

private static void undo(Board board) {
for(int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
board.setElement(boardState.peek().getElement(i, j), i, j);
}
}
}

private static void makeMove(int[] move, Board board) {
pegs--;
if (move[2] == 0) {
board.setElement('O' , move[0], move[1]);
board.setElement('O', move[0]-1, move[1]);
board.setElement('X', move[0]-2, move[1]);
}
if (move[2] == 1) {
board.setElement('O', move[0], move[1]);
board.setElement('O', move[0], move[1]+1);
board.setElement('X', move[0], move[1]+2);
}
if (move[2] == 2) {
board.setElement('O', move[0], move[1]);
board.setElement('O', move[0]+1, move[1]);
board.setElement('X', move[0]+2, move[1]);
}
if (move[2] == 3) {
board.setElement('O', move[0], move[1]);
board.setElement('O', move[0], move[1]-1);
board.setElement('X', move[0], move[1]-2);
}
}

private static int[] findMove(int[] move, Board board) {
int i,j,k;
for (i = 0; i < 7; i++) {
if (move[0] <= i) {
for (j = 0; j < 7; j++) {
if (move[1] <= j || move[0] < i) {
for (k = 0; k < 4; k++) {
if (move[2] <= k || move[1] < j) {
if (board.getElement(i, j) == 'X') {
if (k == 0 && i > 1 && board.getElement(i-1, j) == 'X' && board.getElement(i-2, j) == 'O') {
move[0] = i;
move[1] = j;
move[2] = k;
return move;
}
if (k == 1 && j < 5 && board.getElement(i, j+1) == 'X' && board.getElement(i, j+2) == 'O') {
move[0] = i;
move[1] = j;
move[2] = k;
return move;
}
if (k == 2 && i < 5 && board.getElement(i+1, j) == 'X' && board.getElement(i+2, j) == 'O') {
move[0] = i;
move[1] = j;
move[2] = k;
return move;
}
if (k == 3 && j > 1 && board.getElement(i, j-1) == 'X' && board.getElement(i, j-2) == 'O') {
move[0] = i;
move[1] = j;
move[2] = k;
return move;
}
}
}
}
}
}
}
}
move[0] = 0;
move[1] = 0;
move[2] = 0;
return move;
}

}
``````