Enumerating Paths Through a Square Grid

Our next combinatorial problem is that of printing all possible paths from a start location to a target location.

Suppose we have a rectangular grid with a robot placed at some starting cell. It then has to find all possible paths that lead to the target cell. The robot is only allowed to move up or to the right. Thus, the next state is generated by doing either an "up move" or a "right move".

Backtracking comes to our rescue again. Here is the pseudo-code that allows the enumeration of all paths through a square grid:

xxxxxxxxxx

routine: enumeratePaths

input: Grid m*n

output: Display all paths

assumption: result is empty to begin with

​

Base case 1:

1. If target is reached then print the path

Base case 2:

2. If left or right cell is outside the grid then stop

​

Recursive case:

1. Add the current cell to path

2. Invoke enumeratePaths to find all paths that are possible by doing an "up" move

3. Invoke enumeratePaths to find all paths that are possible by doing a "right" move

4. Remove the current cell from path