Simple 2x2 open grid
Input
[[0,0],[0,0]]
Output
['DR', 'RD']
Two shortest non-revisiting paths: Down->Right and Right->Down. Sorted lexicographically yields ['DR', 'RD'].
Full lesson preview
Find all paths through a maze
Use backtracking to discover every valid path from the top-left to the bottom-right of a grid maze.
Python practice16 minRecursion & BacktrackingIntermediateLast updated March 27, 2026
Problem statement
Given a 2D grid representing a maze where 0 indicates an open cell and 1 indicates a wall, find all distinct paths from the start cell (0, 0) to the goal cell (n-1, m-1). You may move up, down, left, or right and cannot move outside the grid or onto walls. Each cell may be visited at most once per path. Represent each path as a string of characters 'U', 'D', 'L', 'R' corresponding to moves from the start to the goal. When the start equals the goal (single open cell), that is one valid path represented by the empty string ''. Return a list of move strings sorted lexicographically. If there are no paths, return an empty list.
Task
Implement a DFS/backtracking routine that explores the grid, avoids walls and revisits, and returns all move-sequence solutions sorted lexicographically.
Examples
Input format
A single argument: maze — a list of lists of integers (0 for open, 1 for wall).
Output format
A list of strings. Each string is a sequence of 'U','D','L','R' showing moves from (0,0) to (n-1,m-1). The list must be sorted lexicographically.
Constraints
1 <= n, m <= 8 (small to allow exhaustive search); cells contain only 0 or 1. Do not revisit cells within the same path.
Samples
Sample 1
Input
[[0,1,0],[0,1,0],[0,0,0]]
Output
['DDRR']
Walls force a unique path: Down, Down, Right, Right.