java - 跳棋棋步生成的递归有什么问题？

Question

我正在用 Java 编写一个简单的跳棋游戏。到目前为止，最困难的部分是生成一个棋子可能的跳跃列表，特别是当有多个路径可以跳跃时。我有这个递归来找到所有可能的路径来进行一系列的跳转。这是一些代码:

/*
 * possibleJumps(Square pos, Board b, Move jump, ArrayList<Move> moves)
 * Add all possible jumps from the position b on board b to movelist moves. 
 */
void possibleJumps(Square pos, Board b, Move jump, ArrayList<Move> moves) {

    ArrayList<Move> simpleJ = this.simpleJumps(pos, b);

    //jump.addJumpSquare(pos);
    //System.out.println("check jump " + pos + " so far:" + jump);

    if (simpleJ.isEmpty()) {
        // no more jumps -> end this jump and add it to the list
        jump.endJump(pos);
        moves.add(jump);
        System.out.println("found jump" + jump);
        return;
    }

    for(Move j:simpleJ) {
        jump.addJumpSquare(j.jumped.get(0));    // add the jumped square to the jump path
        possibleJumps(j.to, b.doMove(j), new Move(jump), moves);
    }
}

只是为了解释一下:simpleJumps 生成一个可能跨越一个方 block 的跳跃列表(所以基本上是所有攻击 Action )。效果很好。

这是测试板:

    A   B   C   D   E   F   G   H
  ---------------------------------
1 |   | o |   |   |   |   |   |   | 1 (0)
  ---------------------------------
2 |   |   |   |   |   |   |   |   | 2 (1)
  ---------------------------------
3 |   | o |   | o |   | o |   | o | 3 (2)
  ---------------------------------
4 |   |   |   |   |   |   |   |   | 4 (3)
  ---------------------------------
5 |   | o |   | o |   | o |   | o | 5 (4)
  ---------------------------------
6 |   |   |   |   |   |   |   |   | 6 (5)
  ---------------------------------
7 |   | o |   | O |   | o |   |   | 7 (6)
  ---------------------------------
8 | x |   |   |   |   |   |   |   | 8 (7)
  ---------------------------------

这是我得到的输出:

found jumpa8c2 via b7-b5-b3-

found jumpa8c2 via b7-b5-d5-d3-

found jumpa8g2 via b7-b5-d5-d3-f3-

它应该是:

found jumpa8c2 via b7-b5-b3-

found jumpa8c2 via b7-d5-d3-

found jumpa8g2 via b7-d5-f3-

原则上，这非常类似于: Print all paths from root to leaf in a Binary tree我读过并曾经了解过这些内容，但我遗漏了一些可能非常简单的东西......

有什么想法吗？

Answer 1

在这个循环中

for(Move j:simpleJ) {
    jump.addJumpSquare(j.jumped.get(0));    // add the jumped square to the jump path
    possibleJumps(j.to, b.doMove(j), new Move(jump), moves);
}

您对所有可能的移动重复使用相同的跳跃 - 如果您有 3 个可能的移动 x、y、z，您最终会将 x、y 和 z 添加到跳跃路径中。

所以你要么必须

1. 在每次迭代时创建一个新的跳转对象(具有适当的状态)或
2. 在迭代结束时删除添加的方 block