Unique Paths III: Walk Every Square Exactly Once

You are given a 2D grid where each cell is one of four values: 1 (start), 2 (end), 0 (empty), or -1 (obstacle). Your job is to find the number of paths from the start cell to the end cell that walk over every empty cell exactly once. You can move up, down, left, or right, but you cannot revisit cells or step on obstacles.

This is LeetCode 980: Unique Paths III, and it sits in a different category than its siblings Unique Paths and Unique Paths II. Those problems count paths in a grid where you can only move right or down. This one lets you move in all four directions, but demands that every walkable cell gets visited. That constraint changes the entire approach from dynamic programming to backtracking.

The problem

The grid is small (at most 20 cells), which is a strong hint that brute force exploration is expected. You need to count every path that starts at 1, ends at 2, and touches every 0 cell along the way. Obstacles (-1) are off-limits.

The brute force approach

The most natural approach is to try every possible path. From the start cell, explore all four neighbors. For each neighbor, explore its neighbors, and so on. When you reach the end cell, check whether you have visited every walkable cell. If yes, count it. If not, discard it.

This is essentially a depth-first search over all possible orderings of the walkable cells. Because the grid has at most 20 cells, the maximum number of walkable cells is around 18 or so. The number of permutations is bounded by 18!, but in practice, the grid structure and obstacles prune most branches early. The brute force approach is the intended solution here.

The key insight

The trick that makes the backtracking clean is modifying the grid in place. When you visit a cell, mark it as -2 (or any negative value) so it behaves like an obstacle for deeper recursive calls. When you backtrack, restore it to 0. This avoids maintaining a separate visited set and keeps the code tight.

Step-by-step walkthrough

The code

def uniquePathsIII(self, grid):
    rows, cols = len(grid), len(grid[0])
    empty = 1
    start_r = start_c = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0:
                empty += 1
            elif grid[r][c] == 1:
                start_r, start_c = r, c

    def dfs(r, c, remaining):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] < 0:
            return 0
        if grid[r][c] == 2:
            return 1 if remaining == 0 else 0
        grid[r][c] = -2
        result = (dfs(r + 1, c, remaining - 1) +
                  dfs(r - 1, c, remaining - 1) +
                  dfs(r, c + 1, remaining - 1) +
                  dfs(r, c - 1, remaining - 1))
        grid[r][c] = 0
        return result

    return dfs(start_r, start_c, empty)

The function starts by scanning the grid to count every walkable cell (all 0 cells plus the start cell itself, since the path must include the start). It records the start position along the way.

The dfs function takes a row, column, and the number of remaining cells to visit. If the position is out of bounds or blocked (any negative value, including our -2 marker), it returns 0. If the position is the end cell, it returns 1 only when remaining is 0, meaning every walkable cell has been visited. Otherwise, it marks the current cell as visited by setting it to -2, recurses in all four directions with remaining - 1, then restores the cell to 0 before returning. That restore step is the backtracking.

Complexity analysis

Time: O(3^N) where N is the number of walkable cells. At each step you have at most 3 unvisited neighbors (you came from one direction, so the fourth is already visited). In the worst case with ~20 cells this is very manageable.

Space: O(N) for the recursion stack. The maximum depth is the number of walkable cells, and we modify the grid in place instead of using a separate visited structure.

The building blocks

Backtracking on a grid

The core pattern here is grid backtracking: explore a cell, mark it visited, recurse in all directions, then unmark it. You will see this exact pattern in Word Search, where you search for a word by walking through adjacent cells. The only difference is the termination condition. In Word Search, you stop when you have matched all characters. Here, you stop when you have visited all walkable cells and reached the end.

Counting with a remaining counter

Instead of checking "have I visited everything?" by scanning the grid each time, you maintain a counter that starts at the total walkable count and decrements with each step. When the counter hits 0 at the end cell, you know the path is complete. This technique applies to any backtracking problem where you need to verify that all items have been consumed.

Edge cases

• No empty cells: If the start cell is adjacent to the end cell and there are no 0 cells, the only valid path is the direct step from start to end. empty starts at 1 (for the start cell), and after stepping onto the end cell with remaining = 0, you get 1 path.
• Fully blocked neighbors: If the start cell is surrounded by obstacles and the end cell, and there are empty cells elsewhere, the answer is 0 because those cells can never be reached.
• Single row or column: The grid might be 1xN or Nx1. The DFS still works because it tries all four directions, and out-of-bounds checks handle the two missing directions.
• Start and end are adjacent: If they are neighbors and there are empty cells, you cannot go directly from start to end because that would skip the empty cells. The remaining check catches this.
• Maximum grid size: The grid can be at most 4x5 = 20 cells. Even with all cells walkable (18 empty + start + end), the backtracking finishes quickly because grid adjacency limits branching.
• Multiple obstacles: Obstacles might split the grid into disconnected regions. If the end cell is in a region unreachable from the start, every DFS branch returns 0 naturally.

From understanding to recall

You now know how to count Hamiltonian paths on a small grid using backtracking. The key details are: count walkable cells up front, use a remaining counter to verify completeness, and mark/unmark cells in place to avoid a separate visited set. Those three details are what you need to reproduce this solution from scratch.

Under interview pressure, the easy mistake is forgetting to include the start cell in the walkable count (that is why empty starts at 1, not 0) or forgetting to restore the cell after backtracking. Spaced repetition helps you internalize these details so they come automatically when you see a grid backtracking problem.

This problem belongs to a family of backtracking problems where exhaustive search is the only option because the constraint (visit everything exactly once) does not have polynomial-time shortcuts. Recognizing that family - and knowing the grid backtracking template - lets you solve these problems confidently without second-guessing whether a DP approach exists.

Related posts

• Unique Paths - The foundation: counting paths in a grid with only right/down moves using DP
• Unique Paths II - Adding obstacles to the DP approach, which works when movement is restricted
• Word Search - Another grid backtracking problem using the same mark/unmark pattern