Paths and words in a grid

A list of strings, one per row, can hold a maze, a word search or the plan of a garden, with # for a wall and . for an open cell. A search for paths through it starts at one cell and keeps stepping to a neighbor (down, up, right or left), one cell per call: each step is a choice, and the neighbors are the options. The search must remember which cells the current path already covers and never step onto one of them again. Otherwise two open cells side by side would send it back and forth forever.

That memory is a set of (row, col) tuples, on_path, and it works differently from the dist dict of breadth-first search in the graphs module. Breadth-first search wants one shortest way to each cell, so the first visit settles a cell for good. A search for every path can't do that: a cell one path has left behind may be just what another path needs. So a cell goes into on_path when the path steps onto it (choose) and comes out again when the search returns from it (un-choose). This program counts every path from the top-left cell to the bottom-right one that never visits a cell twice:

def count_paths(grid, row, col, on_path):
    if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
        return 0                                  # off the grid
    if grid[row][col] == "#" or (row, col) in on_path:
        return 0                                  # a wall, or already on this path
    if (row, col) == (len(grid) - 1, len(grid[0]) - 1):
        return 1                                  # reached the exit
    on_path.add((row, col))                       # mark: the path is here
    total = (count_paths(grid, row + 1, col, on_path)
             + count_paths(grid, row - 1, col, on_path)
             + count_paths(grid, row, col + 1, on_path)
             + count_paths(grid, row, col - 1, on_path))
    on_path.remove((row, col))                    # unmark on the way back
    return total


maze = ["....",
        ".#..",
        "...."]
print(count_paths(maze, 0, 0, set()))
print(count_paths([".....", ".....", "....."], 0, 0, set()))

7
125

How it works

• Each call first looks at its own cell: off the grid, a wall or a cell already on the path ends the call with 0. That's why the four recursive calls need no checks in front of them: a step to a bad neighbor simply comes back with 0.
• on_path is a set, so adding a cell, asking whether a cell is in it and removing it are all O(1).
• The small maze has 7 paths. Take its wall away and add a fifth column, and there are 125, most of them long and winding: the search follows every one of them to the end.

Forgetting to unmark

Leave out the unmark, and the set works like the visited check of breadth-first search:

def count_paths(grid, row, col, seen):
    if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
        return 0
    if grid[row][col] == "#" or (row, col) in seen:
        return 0
    if (row, col) == (len(grid) - 1, len(grid[0]) - 1):
        return 1
    seen.add((row, col))                          # marked for good
    return (count_paths(grid, row + 1, col, seen)
            + count_paths(grid, row - 1, col, seen)
            + count_paths(grid, row, col + 1, seen)
            + count_paths(grid, row, col - 1, seen))


maze = ["....",
        ".#..",
        "...."]
print(count_paths(maze, 0, 0, set()))

2

The maze has 7 paths, not 2. The first paths that reach the exit leave their cells marked, and every later path that would cross them is blocked, even though it's a different path. There's no error, just a wrong number, so look for the unmark whenever a grid search finds too few paths.

What it costs

The number of paths grows exponentially with the grid: 2 for a 2 × 2 grid, 12 for 3 × 3, 184 for 4 × 4, 8,512 for 5 × 5 and over a million for 6 × 6, and the search visits every one of them. A path can be as long as the grid has cells, and so can the recursion: fine for these small grids, but a path on a 40 × 40 grid could go 1,600 calls deep, past Python's limit of about 1000.

Word search

Word search games hide words in a grid of letters. Each letter of a word sits on a cell next to the one before it (up, down, left or right), and no cell may be used twice in one word. The same kind of search finds them. Any cell could hold the first letter, so start a search from each one in turn. From a cell, matching the word from its letter k on goes like this:

1. If k == len(word), every letter has matched: True.
2. If the cell is off the grid, already on the path, or its letter isn't word[k]: False.
3. Otherwise mark the cell, try the four neighbors with k + 1, unmark the cell, and return whether any neighbor worked.

Two kinds of pruning keep it quick. A cell with the wrong letter ends its branch at once, so the search only follows paths that spell the start of the word. And or stops at the first neighbor that works, so the search ends as soon as one path spells the whole word.