algorithm - 用最少的步骤解决游戏“Pop it”的算法

Question

谁能建议我以最少的步骤解决这个游戏http://puzzle-games.pogo.com/games/poppit的策略。

我的想法是找到一组气球（相同颜色的邻居），这些气球在被移除后留下的组数最少。

然而，我的实现还不够好。我唯一能想到的就是收集所有气球组并检查每个组如果我删除它会剩下多少组。这当然是一项非常繁重的操作，因为它包括在我删除一个组之后重新排列气球，然后恢复原始顺序。

如果有人想出更好的方法来实现我的算法或解决问题的完全不同的方法，我将非常感激！

Answer 1

这个游戏是Same Game的另一个版本。是否存在最优解的问题在本文中被证明是 NP 完全的。这意味着，一般来说，找到一个最佳解决方案需要指数级的时间。另一方面，如果您将问题转化为布尔可满足性问题的一个实例，您可以使用SAT 求解器比临时方法更快地解决问题。

Answer 2

What you have mentioned is the Backtracking approach. You pop groups of balloons until you can't no more, then you undo the the last move and try something else. Wikipedia explains this better than I ever could.

While this sounds computationally heavy, I'm guessing computers these days should be able to solve your problem pretty quickly.

As for implementation, base it on a recursive function (a function that calls itself), the pseudo-code would look something like this:

void main()
{
    setupBoard();
    if(Try())
        print("Found Solution");
}

boolean Try()
{
   if(noballonsLeft)
       return true; //Found solution!
   foreach(Move move in getPossibleMoves())
   {
       doMove(move);
       if(Try())
           return true; //This try found a solution!
       undoMove(move);
   }
   return false; //No solutions found
}

This will find a solution to the problem, extending this to find the best solution should be no problem ;)