Hledání min podle mě není NP-hard. Jak by jste převedl SAT na hledání min?
Počet kroků hry je polynomiální k velikosti herního pole. Předpokládáme-li, že v každém tahu půjde vyplnit alespoň jedno políčko, tak průchod všemi políčky je také polinomiální. A vyřešitelnost případně řešení každého políčka závisí pouze na sousedech, takže to je konstantní složitost.
