Reminds me of Sokoban, which is NP-hard [1]<p>[1] <a href="http://en.wikipedia.org/wiki/Sokoban" rel="nofollow">http://en.wikipedia.org/wiki/Sokoban</a>
I don't understand the reference to lawn-mowing being NP-complete - I thought I had a good algorithm: mow once around the outside, blowing grass inward, to get the edges without hitting things with the exhaust chute, then afterwards mow concentrically, blowing grass outward. Once the width is less than the turning radius of the mower, switch to only mowing along the long axis of the area.<p>Now, when there are rocks, stumps or trees within the area things get more interesting, depending on your tolerance for having to sharpen the blades...
I don't think the author understands what np complete actually means. I don't think that it is easy to verify that a snow Blown path is optimally efficient. It's interesting to discuss the complexity of day to day tasks, but optimal cleaning seems to be np hard, not np complete. You may think that you have the optimal solution until a friend of yours shows you his solution.