Consider a problem where a "robot cleaner" is placed on a room modeled as a grid. Each cell in the grid can be empty or blocked and all accessible cells are connected, meaning, all empty cells will be accessible by the robot regardless of its starting position.

We are told that the robot cleaner can only take one of four actions:

  • move forward
  • turn left (90 degrees, without moving)
  • turn right (90 degrees, without moving)
  • clean the current cell in the grid

We are asked to design an algorithm for the robot to clean the entire room.

My question is: Can this problem be framed as a maze solving problem? I mention this because a common strategy (if the maze is simply connected) for maze solving is to be a "wall follower" (e.g. always try right, or always try left), and I wonder if wall following would work here.

More generally, why would "wall following" be a good strategy for either problem? Isn't it enough to do DFS (with backtracking) even if we pick an arbitrary order of directions that are "left to explore" from each grid position? (or explore directions at a given position in any order?)


1 Answer 1


Try it on some simple examples. You'll quickly see why wall following is not sufficient.

  • 1
    $\begingroup$ Since this answer is flagged as "low-quality because of its length and content", the subject of that flagging action must be an automated process that cannot differentiate authors. $\endgroup$
    – John L.
    May 5, 2020 at 12:15
  • 1
    $\begingroup$ This doesn't seem like it should be posted as an answer IMO. $\endgroup$
    – 6005
    May 5, 2020 at 13:05
  • $\begingroup$ @6005, good point -- I'm not sure it's appropriate as answer either... $\endgroup$
    – D.W.
    May 5, 2020 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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