A variant of travel salesman problem in grid graph
This is similar (but not identical) to the game Zen Puzzle Garden. The important difference for the purposes of your question is that in ZPG you can also have “walkable” squares which the robot (or rather monk, in that game) can walk freely across without leaving a trace.

It is known that ZPG is NP-complete, but our proof makes critical use of these walkable squares and so it does not extend to this problem.

When I was working on the proof above, I spent some time thinking about whether it was possible to show NP-hardness without using walkable squares, but without success. As far as I know the question is still open.