Perhaps Lemmings games can be solved by tree search. If so, it will be a very sophisticated tree search.
First consider a brute force tree search. The actions available to a player can be described as clicking the mouse on a point on the computer screen or doing nothing. An action must be taken at an interval which is less than one second but probably not less than 0.1 seconds. Some parts of the screen are unresponsive, so we can regard doing nothing as clicking on such a place. The screen on a Macintosh PowerBook is 640 by 480 pixels. Thus the player has 307200 choices every 0.1 seconds. Even if the player could fully observe the consequences of each choice, the branching would make tree search of the full tree impractical.
What must we do to make tree search practical? We first consider what reduced trees to use.
Here is where a real difference with previous tree search algorithms must arise. We need to make the division into regions tentative and refine it when this is required.
If we regard this reasoning as tree search, then we consider making the first lemming a blocker as one edge, solving the rest of the game as another edge, see this as a loss, backtrack and put in making the lemming into a floater, etc.
The tree search algorithm itself has to decide in what order to examine the nodes. This clearly requires many heuristics, most specifically considering first moves and sequences of moves that are recommended by some idea. This is where logic will surely creep back in.
It is not obvious that all the above notions can be applied in a way that will reduce the tree search to managable proportions. My intuition is that they can--at least for large parts of many games.
Tree search often becomes inefficient when the sequence of actions is divisible into actions that independently affect different aspects of the situation. Then it usually becomes more efficient to break the problem into parts that can be thought about separately, solve the separate problems and then combine the results. I think Lemmings has enough of this to make a pure tree search algorithm impractical.
(This phenomenon is what makes pure tree search algorithms impractical for Go. It is necessary to consider the different areas of the board separately and then combine the results.)
Lemmings tree searches can include retries of games. For example, when the place a blocker is exploded turns out to be too thin, the program should take another look at the pixel map and find a thicker place to explode the blocker.