On this page
Description
"Every route through the maze" and "can this word be traced through adjacent letters?" walk a grid like a graph traversal, with one crucial difference. A shortest-path BFS visits each cell once, ever. Listing paths must let different paths reuse the same cell; only a single path can't cross itself. So the visited marks belong to the current path: mark a cell when you step onto it, and unmark it when you step back.
We'll go from simple to more technical:
- The pattern: mark on entry, explore four directions, unmark on exit.
- A second flavor: tracing a word, using the board itself as the mark.
- Where path search shows up in production (word games, routing puzzles).
- What breaks it: never unmarking, never marking, and direction order.
The approach
Java
void backtrack(int r, int c, boolean[][] visited, StringBuilder path, List<String> result) {
if (r == n - 1 && c == n - 1) { result.add(path.toString()); return; }
visited[r][c] = true; // on the current path
for (int d = 0; d < 4; d++) { // D, L, R, U - a fixed order
int nr = r + DR[d], nc = c + DC[d];
if (inBounds(nr, nc) && maze[nr][nc] == 1 && !visited[nr][nc]) {
path.append(MOVE[d]);
backtrack(nr, nc, visited, path, result);
path.deleteCharAt(path.length() - 1); // undo the move
}
}
visited[r][c] = false; // off the path: free for other paths
}
Python
def backtrack(r: int, c: int, visited: list[list[bool]], path: list[str], result: list[str]) -> None:
if r == n - 1 and c == n - 1:
result.append("".join(path))
return
visited[r][c] = True # on the current path
for dr, dc, move in MOVES: # D, L, R, U - a fixed order
nr, nc = r + dr, c + dc
if in_bounds(nr, nc) and maze[nr][nc] == 1 and not visited[nr][nc]:
path.append(move)
backtrack(nr, nc, visited, path, result)
path.pop() # undo the move
visited[r][c] = False # off the path: free for other paths
Marking on the way in stops the current path from looping back on itself; unmarking on the way out lets a later path, reached by a different route, pass through the same cell. The fixed move order decides the order results appear: D, L, R, U is alphabetical, and since no complete path is a prefix of another (each one ends at the destination), the paths come out in lexicographic order.
A second flavor: tracing a word
Word Search asks whether a word can be spelled by moving between adjacent cells, using each cell at most once. It's the same per-path marking - usually by temporarily overwriting the cell:
Java
boolean search(char[][] board, String word, int i, int r, int c) {
if (i == word.length()) return true;
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] != word.charAt(i)) return false;
char saved = board[r][c];
board[r][c] = '#'; // used by this path
boolean found = search(board, word, i + 1, r + 1, c) || search(board, word, i + 1, r - 1, c)
|| search(board, word, i + 1, r, c + 1) || search(board, word, i + 1, r, c - 1);
board[r][c] = saved; // restore for other paths
return found;
}
Python
def search(board: list[list[str]], word: str, i: int, r: int, c: int) -> bool:
if i == len(word):
return True
if r < 0 or c < 0 or r >= len(board) or c >= len(board[0]) or board[r][c] != word[i]:
return False # r < 0 matters: board[-1] is the last row
saved = board[r][c]
board[r][c] = "#" # used by this path
found = (search(board, word, i + 1, r + 1, c) or search(board, word, i + 1, r - 1, c)
or search(board, word, i + 1, r, c + 1) or search(board, word, i + 1, r, c - 1))
board[r][c] = saved # restore for other paths
return found
Overwriting the cell doubles as the visited mark with no extra array; restoring it is the unmark. Short-circuiting || stops as soon as one direction succeeds (Python's or does the same). In Python the board has to be a list of lists: strings are immutable, so a row stored as a str can't be overwritten in place.
Where you'll see it
Board-game move generators (word games, puzzles), route enumeration with per-route constraints (a delivery route that may not revisit a stop), and circuit or PCB path search all walk grids with per-path state. When only one path or the shortest path matters, those systems switch to BFS or A* - enumeration is reserved for "all" or "does any exist under per-path rules".
Which tool for which job?
| You need | Use |
|---|---|
| Every path through a grid | DFS with per-path marks: mark, explore, unmark |
| Can a word be traced? | the same, overwriting the cell as the mark |
| Is there any path, or the shortest? | BFS, O(rows × cols) |
| Many words on one board | one walk with a trie of all the words |
| A word that can't fit | letter-count check before searching |
| A word with one rare letter | search from the rarer end |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Never unmarking | 12 corner-to-corner paths on 3 × 3 shrink to 2 | unmark when you step back |
| Never marking | a word reuses a cell ("ABCB" with one B) | mark before recursing |
| Unspecified direction order | right answers, wrong order | use the order the problem gives |
| Enumerating to find any path | exponential work | BFS |
| Searching each dictionary word separately | shared prefixes are redone | a trie |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. What happens if the rat-in-a-maze search never unmarks cells?
Show answer
Cells touched by an earlier path stay blocked for every later path, so most paths are never found - an open 3 x 3 grid reports 2 paths instead of 12. The mark must only last while the cell is on the current path.
2. Why does trying moves in the order D, L, R, U produce the paths in lexicographic order?
Show answer
D < L < R < U alphabetically, and DFS explores all paths starting with an earlier move before any path starting with a later one, at every step. Because each path ends at the destination, no path is a prefix of another, so this order is exactly lexicographic order.
3. How does Word Search mark cells without a visited array?
Show answer
It overwrites the current cell with a character that can't match (such as '#') before exploring neighbors, and writes the original letter back afterwards. The overwrite stops the path from reusing the cell; the restore frees it for other paths.
Key takeaways
- Enumerating grid paths marks cells for the current path only: mark on entry, unmark on exit.
- Never unmarking hides most paths; never marking lets a path reuse cells.
- The fixed move order determines the output order (D, L, R, U gives lexicographic paths).
- Word Search is the same pattern, marking by temporarily overwriting the cell.
- Exponential for enumeration; use BFS when one or the shortest path is enough.