NP hard isn't much of a problem, because the levels are fairly small, and instances are not chosen to be worst case hard but to be entertaining for humans to solve.

SMT/SAT solvers or integer linear programming can get you pretty far. Many classic puzzle games like Minesweeper are NP hard, and you can solve any instance that a human would be able to solve in their lifetime fairly quickly on a computer.