Using recursion to solve Peg Solitaire

Question

The issue I am currently having is my code is failing to solve different variations of a peg solitaire board. My test program tests 4 simple solvable boards. (1 move solutions) one move up, one move down, one move left, one move right. My code solves these with no problems along with testing an unsolvable board. The issue I am having is with solving more complicated problems such as a plus, a rhombus, and a standard board.

I'm not quite sure how to add the recursion to this problem. I have added it at the end of the solveHelp method calling setupMove again but that breaks the rest of my code. Not allowing the simple solutions to be solved correctly.

What would be the best way to apply the recursion for this problem?

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

    // Look at all of the pegs in the board
    for (int x = 0; x < pegs.length; x++) {
        for (int y = 0; y < pegs[x].length; y++) {
            if (pegs[x][y]) {
                startX = x;
                startY = y;

                if (startX <= 5 && pegs[startX][startY] == true
                        && pegs[startX + 1][startY] == true && pegs[startX + 2][startY] == false) {
                    tryMove(pegs, startX, startY, startX + 1, startY, startX + 2, startY);
                }
                if (startX >= 2 && pegs[startX][startY] == true 
                        && pegs[startX - 1][startY] == true && pegs[startX - 2][startY] == false) {
                    tryMove(pegs, startX, startY, startX - 1, startY, startX - 2, startY);
                }
                if (startY <= 5 && pegs[startX][startY] == true 
                        && pegs[startX][startY + 1] == true && pegs[startX][startY + 2] == false) {
                    tryMove(pegs, startX, startY, startX, startY + 1, startX, startY + 2);
                }
                if (startY >= 2 && pegs[startX][startY] == true 
                        && pegs[startX][startY - 1] == true && pegs[startX][startY - 2] == false) {
                    tryMove(pegs, startX, startY, startX, startY - 1, startX, startY - 2);
                }
            }
        }
    }
    if (win) {
        return true;
    } else {
        solution = null;
        return false;
    }
}

public static void tryMove(
        boolean[][] pegs, int startX, int startY, int jumpX, int jumpY, int endX, int endY) {
    pegs[startX][startY] = false;
    pegs[jumpX][jumpY] = false;
    pegs[endX][endY] = true;
    prevSolution = solution;
    solution = solution + " " + startY + " " + startX + " " + endY + " " + endX;
    solveHelp(pegs, startX, startY, jumpX, jumpY, endX, endY);
}

public static void solveHelp(
        boolean[][] pegs, int startX, int startY, int jumpX, int jumpY, int endX, int endY) {
    for (int x = 0; x < pegs.length; x++) {
        for (int y = 0; y < pegs[x].length; y++) {
            if (pegs[x][y]) {
                pegCount++;
            }
        }
    }
    if (pegs[3][3] && pegCount == 1) {
        // WE WIN!!!
        win = true;
    }

    if ((!win && pegCount == 1) || (endX < 0 || endY < 0 
            || endX >= pegs.length || endY >= pegs[endX].length 
            || (endX < 2 && endY < 2) || (endX >= 5 && endY < 2) 
            || (endX < 2 && endY >= 5) || (endX >= 5 && endY >= 5))) {
        pegs[startX][startY] = true;
        pegs[jumpX][jumpY] = true;
        pegs[endX][endY] = false;
        pegCount++;
        solution = prevSolution;
    }
    pegCount = 0;
}

Answer 1

Expressing an algorithm recursively is about writing it as a method that solves the problem by transforming it into slightly simpler versions of itself. Then call the same method recursively to solve those.

The method finally stops the chain of self-calls by checking for one or more "base cases." These are when the problem is so simple that the answer is obvious.

You've chosen a method signature that won't allow a recursive solution. There's no dishonor in this. Getting a usable recursive method signature is a skill acquired through lots of practice.

Here you'll do better if the method accepts just a solitaire board configuration and the number of pegs it contains, say N. Then for each legal way of making a jump, it makes that jump, producing a new version of the board with N-1 pegs. It calls itself to solve this new, smaller problem. The base case is 1 peg, which of course means you win.

void play(boolean [][] board, int nPegs) {
  if (nPegs == 1) { System.out.println("We win!"); System.exit(0); }
  else {
    for (int i = 0; i < 7; ++i) { // i is the row
      for (int j = 0; j < 7; ++j) { // j is the column
        if (!board[i][j]) continue; // No pin. Skip this position
        if (isLegalToJumpEast(board, i, j)) {
          // Do the jump east and solve recursively.
          board[i][j] = board[i][j + 1] = false;
          board[i][j + 2] = true;
          play(board, n - 1);
          // Undo the jump so the search can continue.
          board[i][j] = board[i][j + 1] = true;
          board[i][j + 2] = false;
        }
        // .. similar if()'s for West, North, and South.
      }
    }
  }
}

Of course this skips interesting parts of the problem like printing the solution once it's found.

Also, this algorithm is incredibly wasteful because it will re-evaluate the same board configuration many times. This is totally unnecessary. Once you've explored all possible outcomes of a given board, there's no sense in doing it again.

You can fix this problem by "memoizing" the recursive method. At the start of the method, check a set of already-explored boards and do nothing if the current board is found. Else save a copy in the set and proceed.

The Java details of copying and saving 2d matrices in a Set<> are another topic for you to explore. You might need to figure this out for your algorithm to finish in reasonable time.