Given a grid of letters and a target word, find a path that spells the word one letter at a
time, moving only to an orthogonally adjacent cell (up, right, down, or left — never diagonally),
and never reusing the same cell twice within that one path. Like
N-Queens, Sudoku,
Graph Coloring, and
Hamiltonian Path, there's no formula for this —
the same extend/reject/backtrack discipline applies: commit to a neighbor that matches the next
letter, and the instant no neighbor works, undo the last commitment and try a different one. What's
new here isn't the discipline itself — Hamiltonian Path's visited array already marks
and unmarks vertices exactly this way — it's the domain: a fixed 2D grid with its own built-in
adjacency (no separate edge list to consult) and a specific string to match, not just "visit
everything" or "avoid every conflict."
The board below is the grid classic word-search demos and puzzles use: 3 rows, 4 columns. Pick a word, then press Step or Run. The search tries every occurrence of the word's first letter as a starting cell, in reading order (top-left to bottom-right). From whichever cell the path currently sits on, it checks neighbors in a fixed order — up, right, down, left — and extends into the first one that matches the next needed letter and isn't already used in this path. The moment no neighbor works, the search backtracks: release the current cell and try the next neighbor (or the next starting cell) instead. Cells in the current path are labeled with their position in it (for example "B·2"); if a cell is reused, every position it holds is shown together (for example "B·2,4").
The mark cells visited checkbox below is on by default — the correct behavior, never reusing a cell within one path. Uncheck it and the identical search stops checking whether a candidate neighbor is already part of the path, so a cell can be reused if its letter happens to fit twice. See Pitfalls for exactly what that does to the word "ABCB" on this board.
Checking a candidate neighbor costs O(1): read its letter, compare it to the one
needed next, and — when the visited check is on — confirm it isn't already part of the path. A
mismatch is caught and discarded before it's ever pushed onto the path, so almost none of the
grid's nominal 4-way branching per step ever turns into real recursion. The demo's own default word
makes the payoff concrete: SEE starts from the first occurrence of 'S', at (row 1,
col 0) in reading order — every one of its three neighbors mismatches the needed 'E' immediately,
so that start is abandoned in 4 attempts without ever pushing a second cell. The
second 'S', at (row 1, col 3), does extend: its first candidate for the final 'E' turns out to be a
dead end one step later and gets backtracked out, then the next candidate succeeds. The whole
search — both starts, the dead end, and the successful path — finishes in
11 attempts and 2 backtracks, not the 12 cells × 42 direction-sequences
(192) a search with no letter-matching or bounds-checking at all would have to consider for a
3-letter word.
function wordSearch(grid, word) {
const rows = grid.length, cols = grid[0].length;
const visited = grid.map(row => row.map(() => false));
const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]; // up, right, down, left
function dfs(r, c, idx) {
if (idx === word.length - 1) return true; // matched every letter
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (visited[nr][nc] || grid[nr][nc] !== word[idx + 1]) continue;
visited[nr][nc] = true;
if (dfs(nr, nc, idx + 1)) return true;
visited[nr][nc] = false; // backtrack: undo, try the next direction
}
return false;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] !== word[0]) continue;
visited[r][c] = true;
if (dfs(r, c, 0)) return true;
visited[r][c] = false; // this start doesn't lead anywhere either
}
}
return false;
}Forgetting to mark cells visited lets the search silently reuse one — and changes the answer, not just the work. This isn't a hypothetical: the demo's own checkbox runs the identical search with only that one check removed, on the identical board. With the word set to ABCB and the checkbox on, the search tries A→B→C, needs a second B, finds none it hasn't already used, and backtracks all the way out — releasing C, then releasing B, then abandoning the first 'A' start entirely, then trying and abandoning the second occurrence of 'A' too — four backtracks in all — correctly reporting the word isn't on this board. Uncheck the box and run the exact same word again: A→B→C reaches the same dead end, but this time the neighbor check for the second B no longer excludes (row 0, col 1) just because it's already in the path — it matches, gets reused, and the search reports ABCB found, with the path visiting (row 0, col 1) as both its second and fourth letter. Zero backtracks, wrong answer. A word search that lets a path double back on itself isn't a looser version of the correct one; it accepts words the board doesn't actually contain.
A path doesn't imply every starting point was checked. The reference
implementation above (and the demo) tries every cell matching the word's first letter, not just the
first one found — stopping the outer loop after the first start's dfs call returns
false would silently miss a word that's only reachable from a later occurrence of that
same starting letter. The default word SEE only succeeds here because the search moves on to the
second 'S' after the first one dead-ends at depth zero; a version that gave up after one failed
start would wrongly report SEE as absent from this board.
Time: O(rows · cols · 4L) in the worst case, where
L is the word's length — up to rows · cols starting cells, each
potentially branching 4 ways at each of L steps before a mismatch or the visited check
prunes it. In practice, as the attempt counts above show, letter mismatches cut this down
enormously; the worst case only shows up on adversarial boards built so almost every prefix of the
word appears in almost every direction. Space: O(rows · cols) for the
visited grid, plus O(L) for the path and the recursion stack.
This is the site's fifth Backtracking entry — the same extend/reject/backtrack shape as N-Queens, Sudoku, Graph Coloring, and Hamiltonian Path, this time walking a path through a 2D letter grid's own fixed adjacency instead of a board's columns, a general graph's edges, or an abstract set of colors. See Choosing a Backtracking Strategy for how this page's own every-starting-cell requirement differs from the pure ordering effects the other nine entries show.