Peg接龙找不到回溯的解决方案

Question

我正在为Java中的Peg纸牌游戏开发一个解决方案。然而，我的解决方案似乎无法解决游戏。

我正在使用“标准”版本，所以董事会看起来像：

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

我的Solutions（）方法是这样工作的：

1. 沿方向（向上、向下、向左或向右）移动位置x、y上的销钉
2. 检查电路板是否处于所需状态，如果处于所需状态，请打印电路板并移动，然后退出程序
3. 检查是否还有可以移动的挂钩，如果没有，退出功能
4. 找到第一个可能在一个或多个方向上移动的销钉；调用solve（）来计算这个peg，它就是方向
5. （如果我们到了这里，第4步产生了一个不希望出现的电路板状态）撤销第4步中的操作，并使用peg可能做出的下一个操作（如果有的话）回忆第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中运行了一个多小时，没有任何结果。

我已经测试了方法板。移动（x，y，方向），板。已完成（），电路板。noMoreMoves（），板。集装箱箱（x，y），板。获取（x，y）和板的移动。分开移动（x、y、方向），它们似乎都能按预期运行。

在我的实现中，或者在递归/回溯中，我是否缺少一些东西？我很确定解决方案不需要超过2亿次移动。




Answer 1

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

使用一种可以输出电路板状态的方法。另外，写一个可以保存你的电路板的表示，还有一个可以比较两个状态，看看它们是否相同。

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

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

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