java - 递归回溯算法无法解决某些情况

Question

我目前正在编写递归算法来解决 Peg Solitaire 游戏。

该算法需要使用“回溯”的方法来求解棋盘。我想我已经设法得到一个非常接近正确的解决方案。看来我的代码正确地解决了所有可解决板的问题。它似乎也能正确确定棋盘何时不可解，但前提是钉子的数量不太高。

我的递归方法是这样的:

public static void solve()
{
    if(isSolved())
    {
        long endTime=System.currentTimeMillis();
        System.out.println("Solved");
        solved=true;
        printArr(board);

    }
    else
    {
            for(int i=0;i<7;i++)
            {
                for(int j=0;j<7;j++)
                {
                    for (int k=0;k<4;k++)
                    {
                        if(makeMove(new int[]{i,j,k}))
                        {
                            if(solved!=true)
                            {
                                solve();
                                undoMove();
                            }
                        }


                    }
                }
            }
        }
    }

棋盘是标准的 Peg Solitaire 棋盘。我确信我的 isSolved() 方法可以正确确定棋盘是否已求解。我的 makeMove 函数接受一行、一列和方向(i、j 和 k)。它会在这些坐标处找到 Hook ，并检查它是否可以按要求的方向移动它。如果可以，它会进行移动，将移动添加到移动数组中，然后返回 true。如果不是，则返回 false。

我的撤消方法弹出数组中的最后一步，并将棋盘恢复到之前的布局(在弹出的移动之前)。

似乎对于具有大约 25 个或更多钉子的随机木板，程序根本不会终止。它无限期地继续处理。可解板和各种具有较少钉子的不可解板似乎始终在 10 秒内终止并获得正确结果。

有什么想法吗？

Answer 1

由于木桩纸牌中的每一步移动都会移除木桩，因此您不可能循环回到之前的状态:比如说，在简单的路径规划中，机器人可能永远在两个方 block 之间来回移动。所以不是这样。

那么你的算法错了吗？在这里，为简单起见减少了:

solve (board state) is

if the board is solved, record success
else
   for all possible moves from this board state
      if move is possible
        make it
        call solve
        undo the move

这个算法不可能让你陷入循环；当它递归时，它会深入搜索空间(即它会移动)。所以不是这样。

有可能你在某些你没有展示的功能上有错误(make move，undo move)。如果 make move 不执行任何操作，那么无论问题有多大，您的程序都不会结束。

然后我得出结论，问题是非常大的搜索问题可能需要很长时间。你可以玩问题的大小。如果它适用于大小为 N 的问题，它是否适用于大小为 N+1 的问题？花几秒钟来解决一个大小为 N 的问题表明你可以忘记让它解决 N+10(我说，基于类似问题的经验):不仅仅是因为它是一个指数问题，而且因为你可能会因为系统尝试获取足够的内存。

有时，一种解决方案是跟踪您已经尝试过的节点，以减少冗余搜索。我怀疑您在这个问题上不会得到太多帮助——您无法保留访问状态列表(这将占用指数内存)，并且保留前几个级别的访问状态列表不会扩展深度您可以搜索到的内容。

这一切都有助于其他人得出的结论:这只是一个大问题。