尝试回溯算法

Question

好吧，所以我想尝试编写一个回溯算法来解决一个简单的游戏。规则如下：最上面一排有一块有 5 个槽的三角形板。有 5 行，每行比上一行少 1 个插槽。除了最底行之外，每个槽都被一根棍子占据。您可以通过拿起棍子 A、跳过相邻的棍子 B 并将 A 插入空插槽来移除棍子。这样做会将 B 棒从板上移除。目标是只剩下一根棍子。我的代码表示如下：

    private static int[] row1 = {1,1,1,1,1};
    private static int[] row2 =  {1,1,1,1};
    private static int[] row3 =   {1,1,1};
    private static int[] row4 =    {1,1};
    private static int[] row5 =     {0};

    private static int[][] all = {row1,row2,row3,row4,row5};
    private static int value = 14;

    private static List<Move> history = new ArrayList<>();

在这个起始位置，只能进行 2 次移动：您可以将第 3 行中的第一根棍子移动到第 5 行，删除第 4 行中的第一根棍子。或者将第 3 行中的最后一根棍子移动到第 5 行中5、移走第4行的最后一根棍子。总共有6种可能的移动方式： 移动右上角、左上、左、右、右下和左下的棍子。

我编写了函数来检查是否可以在给定方向上移动棍子。我还编写了移动它们和撤消移动的函数。进行一次移动会使棍棒总数（值）减少 1。撤消则相反。

我现在的计划是编写一个回溯算法来尝试第一个可能的动作。如果递归调用解决了整个棋盘问题，则返回 true。否则它应该回溯并尝试下一步。 然而，我的回溯总是回到起点并以循环结束，总是尝试同一组动作......

这就是函数：

private static boolean solveBoard(int[][] board){
        if(value == 1){
            return true; //win condition. Making a move reduces the value by 1.
        }
        List<Move> possible = getAllPossibleMoves(board);
        int lastMoveIndex = -1;
        for(int row = 0; row < board.length; row++){
            for(int col = 0; col < board[row].length; col++){
                if(possible.size() > 0){// if there are possible moves left, execute the 1st
                    for (Move move : possible) {
                        makeMove(move.getBoard(), move.getRow(), move.getColumn(), move.getDirection());
                        lastMoveIndex = possible.indexOf(move);
                        history.add(move);
                        printBoard(board);
                        if (solveBoard(board)) {
                            return true;
                        } else {// backtrack NOT WORKING
                            for(int m = history.size() -1; m >= lastMoveIndex; m--){
                                undoMove(history.get(m));
                            }
                            history.clear();
                            System.out.println("undo");
                            printBoard(board);
                        }
                    }
                }else if(value != 0){// losing condition: no moves, but more than 1 stick
                    return false;
                }
            }
        }
        return true;
    }

我错过了什么？

Answer 1

好吧，我想通了。只是不得不重写一些方法。如果你对完整的源代码感兴趣，我会尽快将其上传到github。

    private static boolean solveBoard(int[][] board, List<Move> possible){
        printBoard(board);
        if(possible.size() == 0){
            return value == 1;
        }
        for(Move move : possible){
            if(solveBoard(makeMove(move),getAllPossibleMoves(makeMove(move)))){
                return true;
            }else{
                undoMove(move);
                printBoard(board);
            }
        }
        return value == 1;
    }

编辑：经过一些更多的更改，代码终于在 github 上！
随心所欲地使用它。