# 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.

• It seems your graph is a partial grid, i.e., a subgraph (might not be induced) of a grid (so a grid is the cartesian product of two path graphs). Hamiltonian path (and cycle) is well-known to be NP-complete for such graphs. So my guess is that your problem is hard as well.
– Juho
Dec 5 '15 at 10:35
• Nice problem! Up to my knowkledge in this "formulation" (visit all cells) it hasn't been studied.
– Vor
Dec 5 '15 at 20:49
• Perhaps you might be able to make a reduction from the Numberlink puzzle game, with the variant that every grid square needs to be visited. This is known to be NP-Hard, but in your case, you would only have one terminal pair, which makes things interesting, as this case is known to be polynomial time solvable. Very interesting indeed. Dec 12 '15 at 20:48
• There was a paper released in 2016 "Traveling Salesman Problem in grids with forbidden neighborhoods" Sep 2 at 19:29