How to find all possible unique paths in a grid?

I have a 3 x 3 grid with randomly placed obstacles in which there is a random starting point but no endpoint. The endpoint is created when there are no more cells to occupy. Movement can occur up, down, left or right.

How can I see all possible unique paths within the grid?

Example:

Once a cell is used when looking for a path, it cannot be used again (1 becomes a 0).
If there are no more neighbouring cells to move into the path has ended. Regardless of weather all the cells have been visited.

# bottom left is (0, 0) and top right is (2, 2)...
# start is (1, 1) and obstacle is (2, 1)
    
[1] [1] [1]
[1] [S] [0]
[1] [1] [1]
    
S = starting point
0 = obstacle
1 = open cell

With the above example there would be 6 unique paths.

path_1 = (1, 2), (2, 2) # up, right
path_2 = (1, 0), (2, 0) # down, right
path_3 = (0, 1), (0, 2), (1, 2), (2, 2) # left, up, right, right
path_4 = (0, 1), (0, 0), (1, 0), (2, 0) # left, down, right, right
path_5 = (1, 2), (0, 2), (0, 1), (0, 0), (1, 0), (2, 0) # up, left, down, down, right, right
path_6 = (1, 0), (0, 0), (0, 1), (0, 2) (1, 2), (2, 2) # down, left, up, up, right, right

Solution

To get all the paths, you can use DFS or BFS but each path needs to have a unique visited set to keep track that you:

do not go back to the same coordinate twice in a single path
allow different paths to go on the same coordinate

I wrote a DFS implementation for a grid here and the solution will rely on this example.

Solution

To do graph search one would need to define the states, which are the coordinates in this case, but for this problem we will keep track of two parameters, for convenience:

The path taken will be documented via Crack code (right=0, down=1, left=2, up=3) which is a form of chain code
the visited set for each path will de documented for the reasons noted above

The implementation in Python is as follows (in my case the top left matches coordinate (0,0) and lower right matches (n-1,n-1) for nXn grid)

import collections
def find_paths(grid, start_coord):
    paths       = set()  # paths will be added here
    state_queue = collections.deque([]) # Pending states which have not been explored yet
    # State is a tuple consists of:
    # 1. current coordinate
    # 2. crack code path
    # 3. set of visited coordinates in that path
    state       = [start_coord, [], {start_coord}]  # Starting state
    while True:
        # Getting all possible neighboring states
        # Crack code (right=0, down=1, left=2, up=3)
        state_right = [(state[0][0],state[0][1]+1), state[1] + [0], state[2].copy()] if state[0][1]+1 < len(grid[state[0][0]]) else None
        state_down  = [(state[0][0]+1,state[0][1]), state[1] + [1], state[2].copy()] if state[0][0]+1 < len(grid) else None
        state_left  = [(state[0][0],state[0][1]-1), state[1] + [2], state[2].copy()] if state[0][1]-1 >= 0 else None
        state_up    = [(state[0][0]-1,state[0][1]), state[1] + [3], state[2].copy()] if state[0][0]-1 >= 0 else None
        # Adding to the queue all the unvisited states, as well as to the visited to avoid returning to states
        blocked_counter = 0
        for next_state in [state_right, state_down, state_left, state_up]:
            if next_state is None:
                blocked_counter += 1
            elif next_state[0] in state[2] or grid[next_state[0][0]][next_state[0][1]] == 0:
                blocked_counter += 1
            else:
                next_state[2].add(next_state[0])
                state_queue.append(next_state)
                
        # After checking all directions' if reached a 'dead end', adding this path to the path set
        if blocked_counter == 4:
            paths.add(tuple(state[1]))
        # Popping next state from the queue and updating the path if needed
        try:
            state = state_queue.pop()
        except IndexError:
            break
    return paths

Explanation

At the beginning we create the initial state, as well as the initial path which is an empty list and the visited set, containing only the start coordinate
For each state we are in we do the following: 2.1. create the four neighboring states (advancing right, up, left or down)

2.2. checking if we can advance in each direction by checking if the path we are in already visited this coordinate and if the coordinate is valid

2.3. if we can advance in the said direction, add this next_state to the state_queue as well as to the visited set of the path

2.4. if we can not advance in any of the four directions, we reached a 'dead end' and we add the path we are in to the paths set

2.5. pop the next state from state_queue which is kind of a bad name since it is a stack (due to the appending and popping from the same side of the deque()
When the state_queue is empty, we finished the search and we can return all the found paths

When running this with the given example, i.e.

start_coord = (1,1)
grid = [[1, 1, 1],
        [1, 1, 0],
        [1, 1, 1]]

We get:

find_paths(grid, start_coord)
# {(2, 3, 0, 0), (3, 2, 1, 1, 0, 0), (3, 0), (2, 1, 0, 0), (1, 0), (1, 2, 3, 3, 0, 0)}