0

我正在为 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() 方法是这样工作的：

  1. x,y在 a 的位置上移动钉子direction（上、下、左或右）
  2. 检查板子是否处于所需状态，如果是，则打印板子和所采取的动作并退出程序
  3. 检查是否还有一个可以移动的钉子，如果没有则退出该功能
  4. 找到第一个可以向一个或多个方向移动的钉子；为那个钉子和它的方向调用solve()。
  5. （如果我们到达这里，第 4 步产生了不希望的棋盘状态）撤消在第 4 步中进行的移动，并使用该挂钩可能进行的下一个可能移动（如果有）调用第 4 步。
  6. 返回到步骤 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 亿次移动。

4

1 回答 1

0

你需要的是一个调试策略。

使用将输出电路板状态的方法。还要写一个来保存你的电路板的表示，以及一个比较两种状态以查看它们是否相同的方法。

第一种方法失败后的输出，然后在回溯后的不同点，以确保回溯已经回溯到正确的轨道。

还要确保您不会多次跟踪同一个动作。

至于可能的移动次数，不要太确定。人们不会先验地认为，在国际象棋的前 10-20 步中，有数十亿种可能的步法，但确实存在。

于 2013-04-07T00:03:07.733 回答