java - 使用递归解决 Peg Solitaire

Question

我当前遇到的问题是我的代码无法解决钉子纸牌的不同变体。我的测试程序测试了 4 个简单的可解板。 (1步解法)上一步、下一步、左一步、右一步。我的代码毫无问题地解决了这些问题，并测试了无法解决的板。我遇到的问题是解决更复杂的问题，例如加号、菱形和标准板。

我不太确定如何将递归添加到这个问题中。我已将其添加到再次调用 setupMove 的solveHelp 方法的末尾，但这会破坏我的其余代码。不允许正确解决简单的解决方案。

应用递归解决此问题的最佳方法是什么？

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

递归地表达算法就是将其编写为一种方法，通过将其转换为稍微简单的版本来解决问题。然后递归调用相同的方法来解决这些问题。

该方法最终通过检查一个或多个“基本情况”来停止自调用链。当问题如此简单以至于答案显而易见时。

您选择的方法签名不允许递归解决方案。这并没有什么耻辱。获得可用的递归方法签名是一项通过大量练习获得的技能。

如果该方法只接受纸牌板配置及其包含的钉子数量(例如 N)，那么您会做得更好。然后，对于每种合法的跳跃方式，它都会进行跳跃，产生新版本的带有 N-1 个钉子的木板。它要求自己解决这个新的、更小的问题。基本情况是 1 个 Hook ，这当然意味着您赢了。

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

当然，这会跳过问题中有趣的部分，例如找到解决方案后打印解决方案。

此外，该算法非常浪费，因为它会多次重新评估相同的板配置。这是完全没有必要的。一旦你探索了给定董事会的所有可能结果，就没有再做一遍的意义。

您可以通过“内存”递归方法来解决此问题。在该方法开始时，检查一组已经探索过的板，如果找到当前板，则不执行任何操作。否则，在集合中保存一份副本并继续。

在 Set<> 中复制和保存二维矩阵的 Java 详细信息是您要探索的另一个主题。您可能需要弄清楚这一点，以便您的算法能够在合理的时间内完成。