There is a nuance when it comes to computational complexity. It is true that you can construct Lemmings levels that are in effect encodings of computer science problems having specific classes of complexity. So any algorithm for solving Lemmings levels, no matter how good, will inevitably run into trouble with some levels--if an algorithm can correctly and efficiently solve any level there is, they would in effect also be able to correctly and efficiently solve those equivalent computer science problems that have eluded researchers for decades (and are generally believed to be not possible to solve efficiently, even if there is no proof of impossibility at present). It's worth pointing out that humans will not fare much better on those kinds of levels either.
But that's a bit different from creating an algorithm that, sure, might not successfully solve literally every solvable level there is, possibly not even every 120 level in the original game, but perhaps can solve, say, Fun or Tricky levels with reasonably high probability of success.
The metric for solution-closeness doesn't have to be perfect. Yes, sometimes it may lead you down a path where you get very close, but can never actually solve the level. This is no different from a human hitting a dead end when solving a level; at some point they'll need to backtrack and explore a different branch of solution to make progress.
All that being said, this will still certainly be challenging even with a lowered goal of say just the Fun levels. I'd suggest doing some research first on what the state of art is for solvers of other puzzle games, for example Sokoban. Maybe looking at the state of art for other kinds of games can also be interesting, though I suspect less applicable to puzzle games like Lemmings. I suspect to make good progress for Lemmings, it will also be necessary for an algorithm to derive a higher-level abstraction or model of the level that is perhaps more based on distinct level areas separated by obstacles (ie. a lot more like how we mentally process levels as we plan out solutions), as opposed to just a raw arrangement of pixels.