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


Read more here: https://stackoverflow.com/questions/68462372/peg-solitaire-solution-program

Content Attribution

This content was originally published by Ryan Bell at Recent Questions - Stack Overflow, and is syndicated here via their RSS feed. You can read the original post over there.

%d bloggers like this: