Backtracking on a grid

Mark a cell as occupied, explore the neighbors, unmark it. The unmark is what makes it a search rather than a flood fill.

Key idea

The choice is a direction

On a grid, each level of the search steps to a neighboring cell. The four directions are the branches, and the cell being stood on has to be marked so the path does not immediately walk back over itself.

The mark is temporary. When the search returns from a cell, that cell becomes available again for other paths, which is exactly the undo step.

1def count_paths(grid, start_row, start_col, length):2    """Paths of the given length that never revisit a cell."""3    rows, cols = len(grid), len(grid[0])4    found = 05 6    def explore(row, col, remaining):7        nonlocal found8        if remaining == 0:9            found += 110            return11        original = grid[row][col]12        grid[row][col] = "#"                       # mark13        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):14            r, c = row + dr, col + dc15            if 0 <= r < rows and 0 <= c < cols and grid[r][c] != "#":16                explore(r, c, remaining - 1)17        grid[row][col] = original                  # unmark18 19    explore(start_row, start_col, length)20    return found21 22board = [["a", "b"], ["c", "d"]]23print(count_paths(board, 0, 0, 2))24print(board)

Complexity· 5 min

Cost of a grid search

Searching for a path of length L from every cell of an m by n grid, with four directions available at each step. Give the time complexity in terms of the cell count and L, and the extra space beyond the grid.

Python

1for row in range(rows):2    for col in range(cols):3        if explore(row, col, 0):4            return True

Problem· 30 min

Word Search

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

CodeGround