Rat in a Maze

+10

A rat starts in the top left cell of an n × n maze, where 1 is an open cell and 0 a wall, and must reach the bottom right cell. Each move goes one cell down (D), left (L), right (R) or up (U) onto an open cell. A path never visits a cell twice and ends at the exit.

Return every path as a string of moves, in alphabetical order, or an empty array if there is none.

Function

findPaths(maze: integer-2d-array) → string-array

mazeinteger-2d-array: the n × n grid, with 1 for an open cell and 0 for a wall
Returnsstring-array: every path from the top left to the bottom right as a string of moves, in alphabetical order

Constraints

2 ≤ n ≤ 5
maze[i][j] is 0 or 1.
Every test maze has at most 2,000 paths. An open 5 × 5 maze has 8,512, so it is not in the tests.

Examples

Input: maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
Output: ["RDDRDR", "RDRDDR"]
Explanation: From the start only the cell to the right is open, and from there only the cell below, so both paths begin RD. RDDRDR sorts first because its third move, D, comes before R.

Follow-up

With all four moves allowed, can you count the paths without listing them? How large can n get before the count is out of reach?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

You must list every path, with no repeats and no gaps. Backtracking does that: extend the path one move at a time, block the cells it uses, and unblock each cell when you step back out of it. Trying the moves in alphabetical order makes the paths come out sorted.

Grow every path breadth first, then sort

Intuition

Keep a queue of partial paths, each with its cell, its used cells and its moves. Take one out and put back every one-move extension onto an open, unused cell, or save it if it reaches the exit. Every path is found exactly once. With at most 25 cells, the used set fits in one integer: bit r * n + c stands for cell (r, c).

The queue hands out paths shortest first, which is not sorted order. In an open 5 × 5 maze the 16-move DDDDRRRULLURRRDD sorts before the 8-move DDDRDRRR. So you sort at the end, and the queue holds a whole layer of partial paths in memory.

Algorithm

If the start or the exit is a wall, return an empty array.
Put the start into the queue: cell (0, 0), used set with bit 0, no moves.
Take the next entry. If it stands on the exit, save its moves and continue.
Otherwise, for each move that lands on an open, unused cell inside the maze, add an entry with that cell, the cell's bit added to the used set, and the move appended.
When the queue is empty, sort the saved paths and return them.

from collections import deque


def findPaths(maze):
    n = len(maze)
    if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
        return []
    moves = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0))
    result = []
    # Each entry is a path in progress: its cell, the cells it has used
    # (bit r * n + c), and its moves so far.
    queue = deque([(0, 0, 1, "")])
    while queue:
        r, c, used, path = queue.popleft()
        if r == n - 1 and c == n - 1:
            result.append(path)
            continue
        for letter, dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
                bit = 1 << (nr * n + nc)
                if not used & bit:
                    queue.append((nr, nc, used | bit, path + letter))
    result.sort()  # shorter paths were found first, so sort by text
    return result

Backtracking in alphabetical order

Intuition

A recursive function stands on a cell. At the exit it saves the moves. Otherwise it sets the cell to 0 so the path cannot come back, tries each move onto an open cell, and sets the cell back to 1, because a later path may pass through it. The memory is the current path and a recursion at most n² deep.

Two paths share their moves up to the first move where they differ, and there the search finishes the smaller letter's branch first. A path also stops at the exit, so no path is the start of another. With the moves tried in the order D, L, R, U, the paths are therefore saved in sorted order.

Algorithm

If the start or the exit is a wall, return an empty array.
Write backtrack(r, c). If (r, c) is the exit, save the current moves and return.
Set maze[r][c] to 0.
For each move in the order D, L, R, U that lands on an open cell inside the maze, append its letter, recurse, and remove the letter.
Set maze[r][c] back to 1. Call backtrack(0, 0) and return the saved paths.

def findPaths(maze):
    n = len(maze)
    result = []
    if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
        return result
    # The moves in alphabetical order, so the paths come out sorted.
    moves = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0))
    path = []

    def backtrack(r, c):
        if r == n - 1 and c == n - 1:
            result.append("".join(path))
            return
        maze[r][c] = 0  # block the cell while this path uses it
        for letter, dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
                path.append(letter)
                backtrack(nr, nc)
                path.pop()
        maze[r][c] = 1  # open it again for the other paths

    backtrack(0, 0)
    return result

Pitfalls and edge cases

Not unmarking a cell when you step back. The cell stays blocked, so no later branch can pass through it. On an open 3 × 3 maze that returns DDRR and DDRURD, 2 of the 12 paths.
Forgetting that the start or the exit can be a wall. A wall at the exit, as in the second example, must give an empty answer, not a path that ends next to it.
Trying the moves in the order down, up, left, right. The set of paths is right but their order is not; D, L, R, U is the alphabetical one.

Frequently asked questions3

What is the time complexity of Rat in a Maze?

After its first move, a path has at most three choices at each cell, and it visits at most n² cells, so there are O(3^(n²)) partial paths, each costing O(n²) to write out. Walls and used cells cut this far down.

Why must the visited mark be removed when backtracking?

The mark has to mean "on the current path", not "seen before". Two different paths may pass through the same cell. If a cell stays marked after the search backs out of it, every later path through that cell is lost.

What if the rat may only move right and down?

Then no path can revisit a cell, so you need no visited marks, and every path has exactly 2n-2 moves. Counting the paths becomes dynamic programming: the ways to reach a cell are the ways to reach the open cell above it plus the ways to reach the open cell to its left.

def findPaths(maze):
    # Write code here

Test #1

Test #2

Argument

maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]

Expected Output

["RDDRDR", "RDRDDR"]