我正在为 Java 中的 Peg Solitaire 游戏开发解决方案。但是，我的解决方案似乎无法解决游戏。
我正在使用“标准”版本，所以板子看起来像：
{2, 2, 1, 1, 1, 2, 2}
{2, 2, 1, 1, 1, 2, 2}
{1, 1, 1, 1, 1, 1, 1}
{1, 1, 1, 0, 1, 1, 1}
{1, 1, 1, 1, 1, 1, 1}
{2, 2, 1, 1, 1, 2, 2}
{2, 2, 1, 1, 1, 2, 2}
0 是空的，1 是钉子，2 是空的
董事会的期望状态是
{2, 2, 0, 0, 0, 2, 2}
{2, 2, 0, 0, 0, 2, 2}
{0, 0, 0, 0, 0, 0, 0}
{0, 0, 0, 1, 0, 0, 0}
{0, 0, 0, 0, 0, 0, 0}
{2, 2, 0, 0, 0, 2, 2}
{2, 2, 0, 0, 0, 2, 2}
我的 solve() 方法是这样工作的：
x,y在 a 的位置上移动钉子direction（上、下、左或右）- 检查板子是否处于所需状态，如果是，则打印板子和所采取的动作并退出程序
- 检查是否还有一个可以移动的钉子，如果没有则退出该功能
- 找到第一个可以向一个或多个方向移动的钉子；为那个钉子和它的方向调用solve()。
- （如果我们到达这里，第 4 步产生了不希望的棋盘状态）撤消在第 4 步中进行的移动，并使用该挂钩可能进行的下一个可能移动（如果有）调用第 4 步。
- 返回到步骤 4 以获取在步骤 4 中找到的挂钩之后的下一个可能挂钩。
我已经像这样实现了上述说明：
private void play(int xx, int yy, Direction direction) {
board.move(xx, yy, direction);
if (board.finished()) {
board.printBoard();
System.out.println(moves);
System.exit(0);
}
if (board.noMoreMoves()) {
return;
}
for (int y = 0; y < board.board.length; y++) {
for (int x = 0; x < board.board[y].length; x++) {
if (board.containsPeg(x, y)) {
Direction[] moves = board.getMovesFor(x, y);
for (Direction move : moves) {
if (move != null) {
this.moves++;
play(x, y, move);
if (move.equals(Direction.UP)) {
board.undoMove(x, y-2, move);
} else if (move.equals(Direction.DOWN)) {
board.undoMove(x, y+2, move);
} else if (move.equals(Direction.LEFT)) {
board.undoMove(x-2, y, move);
} else if (move.equals(Direction.RIGHT)) {
board.undoMove(x+2, y, move);
}
}
}
}
}
}
return;
}
但是，上述解决方案不会产生所需的电路板状态。我现在这个版本在 eclipse 中运行了一个多小时，没有任何结果。
我已经测试了方法 board.move(x, y, direction)、board.finished()、board.noMoreMoves()、board.containsPeg(x, y)、board.getMovesFor(x, y) 和 board.undoMove (x, y, direction) 是孤立的，它们似乎都按预期运行。
我在这里是否缺少一些东西，无论是在我的实现中还是在一般的递归/回溯中？我很确定该解决方案不需要进行超过2 亿次移动。