Agre and Chapman ([Agre and Chapman, 1987]) describe a program for playing the game of Pengo. According to that article, Pengo does not require planning. An adequate game is played by a program that reacts reflexively to rather simple patterns in the position. For example, their program Pengi uses terms like
and propositions like
where the dashes indicate that each of the above two expressions is elementary and encoded by some program.
Since the program is specific to the Pengo game, it doesn't correspond to the human ability to learn the rules and then learn how to play effectively.
A program deciding what to do based on a fixed set of such terms and propositions would not work for Lemmings. Thus winning one of the games requires making the very first lemming into a floater and using this quality only after the last lemming has emerged. Discovering this requires that the program do planning. The argument the program has to make is something like this.
I need to make the first lemming into a blocker, but if I plan to blow him up at the end I won't save all the lemmings--which is required in this game. Therefore, he must be undermined rather than blown up. However, if he is undermined as just a blocker, he will fall to his death when undermined. Therefore, he must be made into a floater before he is made a blocker, i.e. at the very beginning. The very last lemming out of the source must also be made a floater and then a miner.
Actually there is a way out whereby it could be claimed that a reactive strategy will work for Lemmings, but I doubt that the advocates of reactive programs would want to take it. Namely, if we put a sufficiently rich mental structure into the external situation, then we could imagine a reactive program operating mainly in the mental part of the space could do anything a planner can do. It would be interesting to try to work out details of this idea.