用递归法求解Peg Solitaire
我目前遇到的问题是，我的代码不能解决不同变体的挂牌纸牌。我的测试程序测试了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;
}回答 1
Stack Overflow用户
发布于 2019-05-24 09:20:04
递归地表达算法就是将其编写为一种方法，通过将其转换为稍微简单一点的自身版本来解决问题。然后递归地调用相同的方法来解决这些问题。
该方法最终通过检查一个或多个“基本情况”来停止自调用链。在这些情况下，问题非常简单，答案是显而易见的。
您选择的方法签名不允许使用递归解决方案。这没什么丢人的。获得一个可用的递归方法签名是一项通过大量实践获得的技能。
在这里，如果这个方法只接受一个纸牌板的配置和它包含的钉子的数量，比如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.
}
}
}
}当然，这跳过了问题中有趣的部分，比如一旦找到解决方案就打印出来。
此外，此算法非常浪费，因为它会多次重新评估相同的电路板配置。这是完全不必要的。一旦你探索了给定董事会的所有可能结果，再做一次就没有意义了。
你可以通过“记忆”递归方法来解决这个问题。在该方法开始时，检查一组已经探索过的板，如果找到当前板，则不执行任何操作。否则，在集合中保存一份副本，然后继续。
在Set<>中复制和保存2d矩阵的Java细节是另一个要探索的主题。您可能需要弄清楚这一点，以便您的算法在合理的时间内完成。
https://stackoverflow.com/questions/56272273
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号