# Find total number of unique paths in a maze from source to destination

Find the total number of unique paths which the robot can take in a given maze to reach the destination from given source.

Positions in the maze will either be open or blocked with an obstacle. The robot can only move to positions without obstacles i.e. solution should find paths which contain only cells which are open. Retracing the 1 or more cells back and forth is not considered a new path. The set of all cells covered in a single path should be unique from other paths. At any given moment, the robot can only move 1 step in one of 4 directions. Valid moves are:

Go North: (x, y) –> (x – 1, y)
Go West: (x, y) –> (x, y – 1)
Go South: (x, y) –> (x + 1, y)
Go East: (x, y) –> (x, y + 1)

For example, consider below maze in the form of a binary matrix where 0 represents an blocked cell and 1 represents an open cell.

[ 1 1 1 1 ]
[ 1 1 0 1 ]
[ 0 1 0 1 ]
[ 1 1 1 1 ]

We have to find number of unique paths from source to destination. Above maze contains 4 unique paths (marked in blue color)

[ 1 1 1 1 ]      [ 1 1 1 1 ]      [ 1 1 1 1 ]      [ 1 1 1 1 ]
[ 1 1 0 1 ]      [ 1 1 0 1 ]      [ 1 1 0 1 ]      [ 1 1 0 1 ]
[ 0 1 0 1 ]      [ 0 1 0 1 ]      [ 0 1 0 1 ]      [ 0 1 0 1 ]
[ 1 1 1 1 ]      [ 1 1 1 1 ]      [ 1 1 1 1 ]      [ 1 1 1 1 ]

The robot should search for a path from the starting position to the goal position until it finds one or until it exhausts all possibilities. We can easily achieve this with the help of Backtracking. We start from given source cell in the matrix and explore all four paths possible and recursively check if they will leads to the destination or not. We update the unique path count whenever destination cell is reached. If a path doesn’t reach destination or we have explored all possible routes from the current cell, we backtrack. To make sure that the path is simple and doesn’t contain any cycles, we keep track of cells involved in current path in an matrix and before exploring any cell, we ignore the cell if it is already covered in current path.

## Java

Output:
Total number of unique paths are 4

Exercise: Extend the solution to print the paths as well

References: https://www.cs.bu.edu/teaching/alg/maze/

(3 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest

If we changed the question to –
1.we can move only on prime numbers.
2.print longest path in lexicographically such that x1>x2 or x1=x2 then y2 > y1 for the order.

Here is my code please tell me what I am doing wrong-

http://ideone.com/VzWINK