<p>This game is another version of <a href="http://en.wikipedia.org/wiki/SameGame" rel="nofollow">Same Game</a>.  The question of whether an optimal solution exists was shown in <a href="http://arxiv.org/abs/cs.CC/0107031" rel="nofollow">this paper</a> to be NP complete.  What this means is that in general,
an optimal solution will take exponential time to find.  On the other hand, if you turn the problem into an instance of the boolean satisfiability problem, you may be able to use a <a href="http://en.wikipedia.org/wiki/SAT_solver#Algorithms_for_solving_SAT" rel="nofollow">SAT solver</a> to solve the problem more quickly than an ad-hoc approach.</p>
Algorithm for solving the game 'Pop it' in least steps
<p>Can anyone suggest me a strategy for solving this game <a href="http://puzzle-games.pogo.com/games/poppit" rel="nofollow">http://puzzle-games.pogo.com/games/poppit</a> in least possible steps. </p>

<p>My idea is to find the group of balloons (same-colored neighbours) which after being removed leaves us with the fewest number of groups. </p>

<p>My implementation however, is not good enough. The only thing I can think of is collect all groups of balloons and check for each group what would be the number of groups left if I remove it. This of course is quite heavy operation to do since it includes rearranging the balloons after I remove a group and then restoring the original order. </p>

<p>If someone comes up with a better way of implementing my algorithm or a completely other approach to the problem, I would be really thankful!</p>