Print all paths of robot through the grid

Introduction

This is a supplement to the previous post where we were interested in just one path of a robot from top left corner to the bottom right corner. In this post we will print all paths of robot moving through a given grid containing few blocked cells.

The algorithm for this solution remains the same, we just need few tricks to get that right. Here, I will explain the idea behind printing all paths of robot through the grid.

Approach

Here, let us discuss what different we need to do to print all the paths. As we can recall from the previous post, the moment we reached the destination, the code just returned true and it was propagated up the recursion stack and the path was printed.

Here in this post, we will try not to return true when we get to the destination, we just print the path and remove the last cell from the path. The moment we remove the last cell, the code will try to find another alternative, as per the MOVES array.

The same logic is followed when we end up to a blocked cell, where there is no other way out, just remove the last entry in the path and let it try with alternatives if available.

Below is the code for the same

Source Code

Additional Code

This is how one can invoke this method

Explanation

Let me explain this whole thing with the help of the recursion tree and the grid.
Print all paths of robotPrint all paths of robot

I have shaded the blocked cell in the recursion tree as well. So all the paths which contains the shaded node will not contribute to the valid paths. So, there are only three valid paths as per the tree:

  • [(0,0), (0,1), (1,1), (2,1), (2,2)]
  • [(0,0), (1,0), (1,1), (2,1), (2,2)]
  • [(0,0), (1,0), (2,0), (2,1), (2,2)]

It is pretty simple to walk through our algorithm and derive all these paths.

  • The robot starts from (0,0), chooses the (0,1) leg
    • Moves to (0,1) and chooses the (0,2) leg
      • Moves to (0,2) and gets stuck, also there are no alternate moves, so the last node in the path is removed and it goes back to (0,1)
      • It then moves to (1,1)
        • There it has just one option which lets it move to (2,1)
          • From (2,1) it only can move to (2,2). At this point, it reaches the destination and prints the first path.
          • Remember, we remove the last entry in the path list after printing the path, so it reaches back to (2,1)
        • There is no alternate path from (2,1), so it removes the last entry in the path, and lands back to (1,1)
      • There is no alternate path remaining from (1,1), it removes the last entry and reaches back to (0,1)
    • At (0,1) it has no alternate path, so it removes it from the path list and reaches to (0,0)
    • Here, it has one alternate path (1,0) and moves there
      • Next, it chooses the (1,1) leg and moves there
        • At (1,1) it cannot choose the (1,2) leg as it is blocked, so it finds an alternate path at (2,1) and moves there
          • At (2,1) it only has one option, i.e. moving to (2,2). Here it reaches the destination and prints the second path.
          • After printing the path, remove the last entry and reach back to (2,1)
          • As there is no alternate path at (2,1), remove it and move back to (1,1)
        • At (1,1) there is no alternate path remaining, so remove it and move to (1,0)
      • At (1,0) the alternate path is (2,0) which takes it to (2,1) and then to (2,2) and prints the third path

The algorithm ends because there is no more paths to try.

Analysis

The analysis is same as the one in the previous post. Please refer to the Analysis section of the previous post.

  • Safwan Ahmad

    Hi @dharam

    Thanks for the detailed solution for the problem. In my version of this problem robot can move in four directions- Up, Down, Left, Right. But it can’t move to any already visited cell (To avoid cycles). Hence I have to maintain information about cells that have been visited during the exploration for any path.

    My idea is to pass a matrix having visited information during recursive call. Is there any better way to handle this?

    • Hey @safwan_ahmad:disqus

      There are multiple approaches to this.
      1) You can maintain a static list to represent the visited cells.
      2) You can make the grid an Object[][] and for every visited cell, you can change it to a special value