Word Search on a Grid Using Backtracking
The Problem
Given a grid of letters and a word, decide whether the word can be traced through the grid by moving between horizontally or vertically adjacent cells, using each cell at most once in the trace.
Board used on this page (4 rows × 5 columns):
c0 c1 c2 c3 c4
r0 C A R T S
r1 O N E W A
r2 L I T E R
r3 D U S K Y
"CONE" C(0,0) → O(1,0) → N(1,1) → E(1,2) ✓
"WETS" W(1,3) → E(1,2) → T(2,2) → S(3,2) ✓
"WETSUIT" W → E → T(2,2) → S → U → I → T ... the only T
next to I is (2,2), already used in this path ✗
The last example shows why the "each cell once" rule matters: the letters exist, but not along a single non-repeating path.
Mapping It to Backtracking
LEVEL: index i in the word (which letter we are matching) STATE: current cell (r, c) + which cells the path already uses OPTIONS: the 4 neighbours of the current cell VALID IF: inside the grid, not on the current path, letter == word[i] CHOOSE: mark (r, c) as used UN-CHOOSE: unmark (r, c) COMPLETE: i == len(word) - 1 and the letter matched → found
Marking Without a Visited Array
A neat trick: temporarily overwrite the cell with a character that can never match, then put the letter back.
dfs(r, c, i):
if out of bounds or board[r][c] != word[i]: return false
if i == len(word) - 1: return true
saved = board[r][c]
board[r][c] = '#' ← choose (mark)
found = dfs(r+1,c,i+1) or dfs(r-1,c,i+1)
or dfs(r,c+1,i+1) or dfs(r,c-1,i+1) ← explore
board[r][c] = saved ← un-choose (restore)
return found
Note the restore runs even when the word was found, so the caller always gets the board back unchanged.
Tracing "CONE"
Start cells: every cell holding 'C' → only (0,0)
dfs(0,0,'C') match → mark
down (1,0) 'O' match → mark
down (2,0) 'L' ≠ 'N' ✗
up (0,0) '#' ≠ 'N' ✗ ← the mark stops us stepping back
right (1,1) 'N' match → mark
down (2,1) 'I' ≠ 'E' ✗
up (0,1) 'A' ≠ 'E' ✗
right (1,2) 'E' match, last letter → FOUND
restore (1,1)
restore (1,0)
restore (0,0)
Only a handful of cells are touched. Most branches fail on the very first letter comparison — that is the pruning.
Pruning Before the Search Even Starts
1. LENGTH CHECK word longer than R × C → impossible. 2. LETTER-COUNT CHECK Count each letter on the board and in the word. If the word needs more of any letter than the board has → return false. O(R·C + L). 3. START FROM THE RARER END If the word's last letter is rarer on the board than its first, search for the reversed word instead — far fewer start cells, and the answer is identical (a path read backwards is still a path).
The code below includes the letter-count check, then runs the search for several words and confirms the board is restored afterwards.
import java.util.Arrays;
public class WordSearch {
static final int[] DR = {1, -1, 0, 0};
static final int[] DC = {0, 0, 1, -1};
static boolean dfs(char[][] board, String word, int r, int c, int i) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
if (board[r][c] != word.charAt(i)) return false;
if (i == word.length() - 1) return true;
char saved = board[r][c];
board[r][c] = '#'; // choose: mark as on-path
boolean found = false;
for (int d = 0; d < 4 && !found; d++)
found = dfs(board, word, r + DR[d], c + DC[d], i + 1); // explore
board[r][c] = saved; // un-choose: restore
return found;
}
static boolean exists(char[][] board, String word) {
int rows = board.length, cols = board[0].length;
if (word.length() > rows * cols) return false;
int[] have = new int[128], need = new int[128]; // letter-count pruning
for (char[] row : board) for (char ch : row) have[ch]++;
for (char ch : word.toCharArray())
if (++need[ch] > have[ch]) return false;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (dfs(board, word, r, c, 0)) return true;
return false;
}
public static void main(String[] args) {
String[] lines = {"CARTS", "ONEWA", "LITER", "DUSKY"};
char[][] board = new char[lines.length][];
for (int r = 0; r < lines.length; r++) board[r] = lines[r].toCharArray();
char[][] before = new char[board.length][];
for (int r = 0; r < board.length; r++) before[r] = board[r].clone();
String[] words = {"CART", "CONE", "LINE", "WETS", "DUSKY", "RENT", "WETSUIT", "EERIE"};
for (String w : words)
System.out.println(String.format("%-8s %s", w, exists(board, w)));
System.out.println("board unchanged: " + Arrays.deepEquals(board, before));
}
}Output:
CART true
CONE true
LINE true
WETS true
DUSKY true
RENT false
WETSUIT false
EERIE false
board unchanged: true
EERIE is rejected by the letter-count check without any DFS — the word needs three E's and the board has only two. RENT and WETSUIT pass the count check but fail the search: the letters exist, just not along one non-repeating path.
Complexity
R × C grid, word length L.
TIME: O(R · C · 3^L)
R·C possible start cells
first step: up to 4 directions
every later step: up to 3 (the cell you came from is marked)
In practice, most branches die on the first mismatched letter.
SPACE: O(L) recursion depth — the path is at most L cells long.
In-place marking needs no extra visited array.
The letter-count check uses O(alphabet) extra space.
Many Words at Once: Add a Trie
Searching 1,000 words one by one repeats a lot of work — every word starting with "CA" re-explores the same paths. Put all the words in a trie and walk the board and the trie together:
dfs(r, c, trieNode):
ch = board[r][c]
if ch == '#' or ch not in trieNode.children: return ← prefix dead → prune
next = trieNode.children[ch]
if next.word is not None:
record next.word
next.word = None ← avoid recording it twice
board[r][c] = '#'
for each neighbour (nr, nc): dfs(nr, nc, next)
board[r][c] = ch
for every cell (r, c): dfs(r, c, trie.root)
The trie prunes as soon as the current path is not a prefix of any remaining word. A further optimisation removes leaf trie nodes once their word is found, so finished branches are never walked again.
Related Grid Backtracking Problems
"Longest path of increasing values" → DFS + memo (no undo needed: DAG)
"Max gold collected, never revisit a cell" → same mark/unmark DFS, track a sum
"Count paths visiting every open cell" → mark/unmark DFS, check count at end
"Shortest path in a maze" → BFS, not backtracking
"Number of islands" → DFS/BFS flood fill — cells stay
marked, no backtracking needed
The deciding question: may a cell be part of a different path later? If yes, unmark on the way out (backtracking). If no — as in flood fill — leave it marked.
Common Mistakes
Marking before checking the letter. Mark only after the current cell has matched; otherwise you overwrite cells you never actually used and may forget to restore them.
Returning before restoring. if (dfs(...)) return true; inside the direction loop skips board[r][c] = saved. Either restore first, or collect the result in a variable as shown above.
Giving up after the first start cell. Writing return dfs(board, word, r, c, 0) inside the start loop returns the result of the first matching cell only. A failed start must fall through to the next cell; return true only on success, and false after the loop.
Using a global visited array without clearing it. If you use a separate visited array, unmark every cell on the way back; a leftover mark from one start cell blocks paths from the next.
Interview Questions
Q: Why is this backtracking and not plain DFS?
Plain DFS marks a cell as visited once and never revisits it, which is right for questions like "which cells are reachable". Here, a cell rejected by one path may be exactly what another path needs, so the visited mark has to be undone when the path retreats. That undo step makes it backtracking.
Q: How would you speed up the search for one long word?
Run the letter-count check first. Then, if the word's last letter appears less often on the board than its first letter, search for the reversed word — fewer starting cells means fewer roots for the search tree. Both are cheap and preserve correctness.
Q: How does a trie change the complexity for many words?
Without a trie, the cost is roughly the sum over all words of R · C · 3^L. With a trie, shared prefixes are explored once, and the search stops the moment the path is not a prefix of any word. The work becomes bounded by the paths that match some prefix rather than by the number of words.
Summary
- ›Word search is DFS + mark on entry + unmark on exit.
- ›Mark in place with a sentinel like
#and always restore before returning. - ›Worst case O(R · C · 3ᴸ) time, O(L) space.
- ›Cheap pre-checks — length, letter counts, search from the rarer end — often skip the search entirely.
- ›For many words, walk a trie alongside the board.
Next, Common Mistakes collects the bugs that show up again and again across all backtracking problems — with a broken and fixed version of each.
Why must a cell be 'unmarked' after exploring from it?