A variant of travel salesman problem in grid graph

In this problem, a robot is moving around on a rectangular grid and try to traverse and cover the whole grid, but it can only go one direction until it hits the boundaries/obstacles or its own trace. The problem is to determine the starting position and the directions of robot so it can cover the whole grid (also in some situations there can be no solution). An example of this game is shown below, where the starting position is chosen to be near the lower right corner, in this example, robot fail to cover the whole places. The movement constraint of robot is similar to ricochet robot but this robot can only visit a place once. I want to know if this problem has been studied before and if there is efficient algorithm to solve it. Currently I just use depth first search to attack this problem, which is quite slow on a large grid. I think this problem can be transformed into a boolean satisfiability problem. I found that this problem is called full house and is published by Erich Friedman.

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.

StackExchange Computer Science Q#50291, answer score: 2