誰も私にこのゲームを解決するための戦略を提案することはできますhttp://puzzle-games.pogo.com/games/poppit少なくとも可能なステップ。ゲームを解決するためのアルゴリズム「Pop it」以上のステップ
私の考えは、バルーンのグループ（同じ色の隣人）が、削除された後、私たちに最も少数のグループを残すことを見つけることです。
しかし、私の実装は、十分ではありません。私が考えることができるのは、バルーンのすべてのグループを収集し、それを削除すると残っているグループの数を各グループごとにチェックすることだけです。これは、グループを削除して元の順序に戻した後に、バルーンを並べ替えることを含むので、もちろん、これは非常に重い操作です。
誰かが私のアルゴリズムや問題に対する完全に他のアプローチを実装するためのよりよい方法を考え出すと、本当に感謝しています。
あなたが言及したのはBacktrackingです。バルーンのグループをポップアップして、それ以上のことができなくなると、最後の移動を元に戻して別のものを試してみましょう。ウィキペディアは私がこれまで以上にこのことを説明しています。
計算量が重いとは言えますが、最近コンピュータを使用して問題をかなり早く解決できるはずです。実装用として
、再帰関数（自分自身を呼び出す関数）をベースにします、擬似コードは次のようになります：
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
}
これが問題に解決策を見つけるでしょう、最高の解決策を見つけるためにこれを拡張しても問題ありません;）
このゲームはSame Gameの別のバージョンです。最適解が存在するかどうかの問題は、this paperにNP完成と表示されました。これが意味することは、一般的には、 最適解は指数関数的に時間がかかることです。一方、問題をブール値充足可能性問題のインスタンスに変えると、SAT solverを使用して、アドホックなアプローチよりも迅速に問題を解決できる場合があります。