6
$\begingroup$

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.

enter image description here

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Juho
    Dec 5, 2015 at 10:35
  • $\begingroup$ Nice problem! Up to my knowkledge in this "formulation" (visit all cells) it hasn't been studied. $\endgroup$
    – Vor
    Dec 5, 2015 at 20:49
  • $\begingroup$ 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. $\endgroup$
    – user340082710
    Dec 12, 2015 at 20:48
  • $\begingroup$ There was a paper released in 2016 "Traveling Salesman Problem in grids with forbidden neighborhoods" $\endgroup$
    – Snowbody
    Sep 2, 2021 at 19:29

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.