深度优先搜索和回溯拼图-Java 学习之路

我正在尝试在我的算法中添加深度优先搜索以找到Peg Solitaire游戏的解决方案 . 现在看来，当我的算法尚未找到解决方案时，它的退出速度太快了 .

如果电路板上只剩下1个挂钩，则会找到解决方案 .

下面是我的函数 findSolution() ，这是一个递归函数 .

direction 包含在电路板上向上，向下，向左和向右移动的所有坐标 .
doJump 在参数板上移动 .
undoJump 直接撤消 grid 上的移动 .
grid ：是一个类变量，它是当前状态下的游戏网格 .

在添加 seenBoards 之前，该算法运行良好，但我添加了这个，因为它访问的节点太多了 . 我想让它更快 .

public boolean findSolution(int[][] board) {

if(nbPegs == 1) return true;

    for(int rowIndex = 0; rowIndex < rowNb; rowIndex++)
    {
        for(int colIndex = 0; colIndex < columnNb; colIndex++)
        {
            for (Point dir : direction)
            {

                if (isValid(rowIndex, colIndex, dir.x, dir.y)) {
                    int[][] newGrid = doJump(board, rowIndex, colIndex, dir.x, dir.y);
                    if (!seenBoards.contains(newGrid)){
                        grid = doJump(board, rowIndex, colIndex, dir.x, dir.y);
                        seenBoards.add(newGrid);

                        if (findSolution(newGrid)) return true;
                        seenBoards.remove(newGrid);
                        undoJump(rowIndex, colIndex, dir.x, dir.y);

                    }
                }
            }
        }
    }
    return false;
}

所以就像我说的那样，这段代码输出没有解决方案，即使有一个解决方案 . 当它应该是几千个时，它只通过8个节点 .

为什么它提前结束？从seeBoards中删除网格的行是否有错误？

我对Depth First搜索有什么看法？欢迎任何想法！

我正在使用这些指南尝试使其工作：

我还检查了这些其他StackOverflow问题，同时试图了解我的算法有什么问题，但没有运气！

谢谢！

深度优先搜索和回溯拼图

相关问题