用递归法解佩格纸牌

Question

我目前面临的问题是，我的代码无法解决peg纸牌板的不同变体。我的测试程序测试了4个简单的可解电路板。（1移动解决方案）向上移动一次，向下移动一次，向左移动一次，向右移动一次。我的代码解决了这些问题，同时测试了一个无法解决的电路板。我面临的问题是如何解决更复杂的问题，比如加号、菱形和标准板。

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

对这个问题应用递归的最好方法是什么？

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个peg，这当然意味着你赢了。

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

当然，这会跳过问题中有趣的部分，比如一旦找到解决方案就打印出来。

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

你可以通过“记忆”递归方法来解决这个问题。在方法开始时，检查一组已经探索过的电路板，如果找到当前的电路板，则什么也不做。否则在集合中保存一份副本并继续。

Java提供了在集中复制和保存2d矩阵的详细信息