递归回溯算法不能解决某些情况

Question

我目前正在编程一个递归算法解决一个佩格纸牌游戏。

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

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();
                            }
                        }


                    }
                }
            }
        }
    }

有什么想法吗？

Answer 1

因为在peg solitaire中的每一个动作都移除一个peg，所以你不可能循环回到以前的状态：比如说，在简单的路径规划中，机器人可能永远在两个方块之间来回移动。所以不是这样。

那么你的算法错了吗？为了简单起见，它被简化了：

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

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

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