尝试回溯算法

Question

好的，我想试着写一个回溯算法来解决一个简单的游戏。规则如下:有一个三角形板，在顶部排有5个槽。有5行，每一行比上面的行少一个槽。每个插槽，除了最底层的一行，都被一根棍子占据。你可以取下棍子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<>();

在这个起始位置，只有两个移动是可能的:您可以将第3行中的第一个棒移到第5行，移除第4行中的第一个棒，或者将最后一个棒从第3行移到第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上了！你想用就用吧。