Depth First Search and Backtracking in a puzzle

Question

I am trying to add a Depth First Search in my algorithm to find a solution to the Peg Solitaire game. Right now, it looks like my algorithm is quitting too fast when it hasn't found a solution yet.

A solution is found if there is only 1 peg left on the board.

Below is my function findSolution() which is a recursive function.

• direction contains all the coordinates to move up, down, left and right on the board.

• doJump makes the move on the board that is in the parameters.

• undoJump undoes the move on grid directly.

• grid is a class variable which is the game grid in its current state.

The algorithm worked well before I added seenBoards, but I added this because it was visiting way too many nodes. I am trying to make it faster.

public boolean findSolution(int[][] board) {

if(nbPegs == 1) return true;

    for(int rowIndex = 0; rowIndex < rowNb; rowIndex++)
    {
        for(int colIndex = 0; colIndex < columnNb; colIndex++)
        {
            for (Point dir : direction)
            {

                if (isValid(rowIndex, colIndex, dir.x, dir.y)) {
                    int[][] newGrid = doJump(board, rowIndex, colIndex, dir.x, dir.y);
                    if (!seenBoards.contains(newGrid)){
                        grid = doJump(board, rowIndex, colIndex, dir.x, dir.y);
                        seenBoards.add(newGrid);

                        if (findSolution(newGrid)) return true;
                        seenBoards.remove(newGrid);
                        undoJump(rowIndex, colIndex, dir.x, dir.y);

                    }
                }
            }
        }
    }
    return false;
}

So now like I said, this code output that there is no solution, even though there is one. It only goes through 8 nodes when it should be a couple thousand.

Why does it end that early? Is there a mistake with the line where I remove the grid from seenBoards?

What am I missing about the Depth First search? Any ideas are welcome!

I am using these guides to try and make it work:

• http://trevorappleton.blogspot.ca/2015/09/solving-peg-solitaire-using-depth-first.html

• https://blackflux.wordpress.com/2014/04/30/peg-solitaire-brute-force/

I also checked these other StackOverflow questions while trying to understand what is wrong with my algorithm, but no luck!

• Peg solitaire – checking pegs vs. checking holes in a depth-first search
• Peg Solitaire backtracking infinite loop
• Peg Solitaire Solutions with Backtracking
• Depth-First search in Python

Thanks!