cf.completefrontend
RECURSION & BACKTRACKING · CORE

Backtracking on a grid

Explore paths through a grid cell by cell, marking cells as used while you stand on them and clearing the mark when you step back.

Time O(R × C × 3^L)Space O(L)4 practice problemsStep-through picture

The idea

Many grid problems ask for a path with a rule: spell a word by moving between neighboring letters, or walk through every open cell exactly once. A path may not visit the same cell twice.

Grid backtracking starts a search at a cell and tries each of the four neighbors: down, up, right, left. Before going deeper it marks the current cell as used, so the path can't step on it again. When the search returns, it clears the mark. That last part matters: another path may use the cell later.

This differs from a flood fill, which marks cells forever because it only needs to know which cells can be reached. Backtracking cares about each path separately, so the mark lasts only while the cell is on the current path.

An everyday example

Placing stepping stones across a garden

You walk across a garden, putting a stone on each square you step on so you don't walk in circles. At every square you try going forward, back, right, and left. If you get stuck, you step back and pick up the stone you just put down. Other walks can then use that square. When your stones spell the route you wanted, you're done.

How the example maps to the code
In the exampleIn the code
The square you stand ongrid[r][c]
Putting a stone downgrid[r][c] = "#"
Trying the four directionssearch(r + 1, c, ...) and the other three calls
Picking the stone back upgrid[r][c] = letter
Walking off the edge of the gardenr < 0 || c < 0 || r >= rows || c >= cols

From the slow way to backtracking on a grid

  1. The slow way to check if a word hides in a letter grid: list every path of L neighboring cells that never repeats a cell, read its letters, and compare them with the word. From each cell a path can branch up to 4 ways, then 3 ways at every later step, so there are millions of paths even on a small grid, and almost all of them spell nonsense.
  2. The fact to use: a path is wrong as soon as one letter is wrong. If the first cell isn't word[0], no path from it can work. So walk the path one cell at a time, compare each cell with the next letter right away, and stop the moment they differ. Most starts now fail on their first cell.
  3. A path also may not use the same cell twice. So while a cell is part of the current path, mark it. Writing "#" into grid[r][c] is a cheap mark: # never equals a letter, so a marked cell fails the normal letter check, with no extra code and no extra array.
  4. The mark must come off when the path backs away from that cell, because a different path may need the cell later, coming from another side. So save the letter, mark the cell, try the four neighbors with index + 1, then put the letter back. Run that from every cell as a start. That loop is backtracking on a grid.

How it works

  1. Loop over every cell (r, c) as a possible start, and call search(r, c, 0) from each.
  2. In search(r, c, index), if index === word.length, every letter was matched: return true.
  3. Return false if (r, c) is outside the grid or grid[r][c] isn't the letter word[index].
  4. Save the letter in letter and mark the cell as used: grid[r][c] = "#".
  5. Try the four neighbors with index + 1. Stop as soon as one of them returns true.
  6. Restore the cell: grid[r][c] = letter, then return what the neighbors found.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function gridHasWord(grid, word) {
  2. const rows = grid.length;
  3. const cols = grid[0].length;
  4. function search(r, c, index) {
  5. if (index === word.length) return true;
  6. if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
  7. if (grid[r][c] !== word[index]) return false;
  8. const letter = grid[r][c];
  9. grid[r][c] = "#";
  10. const found =
  11. search(r + 1, c, index + 1) ||
  12. search(r - 1, c, index + 1) ||
  13. search(r, c + 1, index + 1) ||
  14. search(r, c - 1, index + 1);
  15. grid[r][c] = letter;
  16. return found;
  17. }
  18. for (let r = 0; r < rows; r++) {
  19. for (let c = 0; c < cols; c++) {
  20. if (search(r, c, 0)) return true;
  21. }
  22. }
  23. return false;
  24. }

How fast it is

TimeO(R × C × 3^L)
Extra memoryO(L)

Each of the R × C starts can branch 3 ways at each of the L letters. The only extra memory is the call chain, one call per matched letter.

  • Best caseO(L)

    The word runs straight down from (0, 0), the first start and the first direction tried. For "DOG" going down the first column, it takes 4 calls.

  • Average caseO(R × C)

    Typical letter grids: few cells match word[0], and most paths die within a letter or two, so the work is mostly one quick check per start cell.

  • Worst caseO(R × C × 3^L)

    Every cell holds the same letter and the word's last letter is missing. A 3 × 4 grid of A with the word "AAAAAAAAAAAAB" takes 13,004 calls to answer false.

Common mistakes

  • Using a visited set that is never cleared. Paths that need a cell already tried by an earlier failed path are wrongly blocked.
  • Checking bounds after reading grid[r][c]. Reading grid[-1] gives undefined, and undefined[c] throws.
  • Restoring the cell only when the search fails. If you return early on success without restoring, the input grid stays changed.
  • Allowing diagonal moves when the problem says only up, down, left, and right.

When to use it

Look for these clues in a problem:

  • The input is a grid of letters, numbers, or open and blocked cells.
  • A path moves between neighboring cells (up, down, left, right) and may not reuse a cell.
  • The question asks whether a path exists, how many paths exist, or which path is best.
  • The grid is small, such as up to 6 × 6 or with few open cells, because paths can be many.

Check yourself

Answer each one in your head first, then open it.

In the trace, why does the call at (1, 2) return true even though that cell holds X?

The first line checks index === word.length. With index = 3, the whole word is already matched, so the call returns before it ever looks at the cell.

Why does writing # into the grid work as a mark?

# never equals a letter of the word, so a marked cell fails the same grid[r][c] !== word[index] check that wrong letters fail. No extra check is needed.

What breaks if the mark is never cleared?

Cells from failed paths stay blocked. For "ABAB" in ["XAB", "ABY"], the first failed start leaves 4 cells marked, and the real path is never found.

Why does the code compute found before restoring the letter, instead of returning straight from the || chain?

So the letter is put back on every path, success or failure. Returning straight from the chain would skip the restore and leave # marks in the grid.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The meaning of a call: search(r, c, index) returns true exactly when the letters word[index] onward can be spelled starting at (r, c), using only cells that aren't on the current path. And when it returns, the grid is exactly as it was when the call began, because the only change it makes is the mark, which it undoes right before returning.

Each line keeps that meaning. If index === word.length, nothing is left to spell, so true is right. A cell off the grid, with the wrong letter, or already on the path (holding #) can't be the next cell, so false is right. Otherwise the cell matches, and the rest of the word must continue from one of its four neighbors, with this cell now on the path. Trying all four covers every way to continue.

The mark has to be cleared. In the grid ["XAB", "ABY"] with the word "ABAB", the first start, (0, 1), fails after marking 4 cells. If those marks stayed, the real path from (1, 0) through (1, 1), (0, 1), and (0, 2) would be blocked, and the answer would wrongly be false. The search ends because every call either returns at once or marks one more cell, so the path is never longer than the word.

Going deeper

3 more ideas

Why the mark must be cleared

The mark means "on the current path", not "seen at some point". Suppose a path through a cell fails. A different path might need that same cell, coming from another side, at another position in the word. If the mark stayed, that second path would be wrongly blocked. Restoring the cell makes each path independent.

Writing the mark into the grid

Changing grid[r][c] to # is a cheap way to mark a cell without an extra array, since # never matches a letter. If you must not change the input, use a separate visited array of true/false values of the same size, and set and clear it in the same places.

The cost

From each start, the first step has 4 directions and every later step at most 3, because you can't go back to the cell you came from. For a word of length L on an R × C grid, the time is O(R × C × 3^L). The memory is the call chain, at most L deep.

Work it by hand

Every step in a table, with why

Look for "SEA" in a 2 × 3 grid. The first path, going down, dead-ends and must be undone before the right path is found. Each row is one call to search.

grid = ["SEA", "EXX"] (as arrays of letters), word = "SEA"

Step(r, c)indexword[index]grid afterWhat happensWhy
1(0, 0)0S#EA / EXXmatch, mark, try downThe first start cell holds S, the first letter. It is marked with #, and down is tried first.
2(1, 0)1E#EA / #XXmatch, mark, try downDown from S is an E. Mark it and look for A around it.
3(2, 0)2A#EA / #XXoutside: falseRow 2 doesn't exist, so the bounds check fails.
4(0, 0)2A#EA / #XXholds #: falseUp is the start cell. It is on the current path, so it holds #, which isn't A.
5(1, 1)2A#EA / #XXholds X: falseRight of (1, 0) is an X.
6(1, -1)2A#EA / EXXoutside, restore (1, 0)Left is off the grid. All four neighbors failed, so (1, 0) gets its E back and returns false.
7(-1, 0)1E#EA / EXXoutside: falseBack at the start cell: up is off the grid.
8(0, 1)1E##A / EXXmatch, mark, try downRight of the start is another E. Mark it and look for A again.
9(1, 1)2A##A / EXXholds X: falseDown is an X.
10(-1, 1)2A##A / EXXoutside: falseUp is off the grid.
11(0, 2)2A### / EXXmatch, mark, try downRight is the A. All three letters are now on the path.
12(1, 2)3none### / EXXindex === 3: trueindex equals word.length, so this call returns true before even looking at the X in this cell. On the way back, (0, 2), (0, 1), and (0, 0) each restore their letter.

gridHasWord returns true after 12 calls, through (0, 0), (0, 1), and (0, 2). The || chain stops at the first direction that works, and every marked cell gets its letter back, so the grid ends exactly as it began.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Backtracking on a gridO(R × C × 3^L)O(L)You need to know if one path spells a word or follows a rule, and each cell may be used only once per path.
Backtracking with a visited arrayO(R × C × 3^L)O(R × C)The same search, when you may not change the input grid or it is shared with other code.
Trie plus one grid searchO(R × C × 3^L)O(W)You must find many words in the same grid, and running one search per word would repeat the same walks. The trie holds W letters, the total length of all the words.
Flood fillO(R × C)O(R × C)You only need to know which cells can be reached, not which paths exist. Marks stay forever, so each cell is visited once.

Extra memory: O(L): the call chain is at most one call per letter, plus one. Marking cells in the grid itself needs no extra array.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Backtracking on a grid and the other approaches, on a scale where each line up is 10 times more steps.
  • Backtracking on a grid O(R × C × 3^L)
  • Backtracking with a visited array O(R × C × 3^L)
  • Trie plus one grid search O(R × C × 3^L)
  • Flood fill O(R × C)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Backtracking on a grid6 millionmore than a quadrillionmore than a quadrillion
Backtracking with a visited array6 millionmore than a quadrillionmore than a quadrillion
Trie plus one grid search6 millionmore than a quadrillionmore than a quadrillion
Flood fill1001 million1 trillion

Inputs that need care

5 tricky inputs
A word that would need a cell twice: "ABA" in ["AB"]
After A and B, the only A is marked #, so the search returns false. That is correct: a cell may not be reused.
A one-letter word
The first cell with that letter matches, and its first neighbor call has index === 1, so it returns true, even if that neighbor is off the grid.
An empty word: ""
The first call has index === 0 === word.length, so it returns true at once. Decide whether the problem wants that, and check it first if not.
An empty grid: []
grid[0].length throws a TypeError. Return false first when grid.length === 0.
A word longer than the grid has cells
No path can be that long, so the answer is false. The search finds that out slowly; checking word.length > rows * cols first answers at once.

Variations and follow-ups

Twists interviewers add

Keep the input unchanged

Use a separate visited array of true/false values, the same size as the grid. Set visited[r][c] = true where the code writes #, and set it back to false where it restores the letter. It costs O(R × C) extra memory.

Many words at once

Put all the words in a trie, a tree of letters where each path from the root spells a word start. Walk the grid once from each cell, moving down the trie as you match letters, and record a word whenever you reach its end. Words that share a start share the work.

Count or find the best path

To count every path that fits a rule, don't stop at the first true: add up the results of all four directions. To find the longest or cheapest path, return a number from each call and keep the best one.

Quick early checks

Count each letter in the grid first. If the word needs more of some letter than the grid has, return false at once. If the word's last letter is rarer than its first, search for the reversed word instead, so fewer paths get started.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from a grid of letters or cells, moves between "adjacent" cells (up, down, left, right), and a rule like "the same cell may not be used more than once".
  • Explain the meaning of the mark out loud: # means "on the current path", not "seen before". Then say why it is cleared on the way back: another path may need that cell later.
  • Test a one-letter word, a word that would need a cell twice, and a word whose only start is in the last cell. Also check that the grid is unchanged after the call.
  • Expect "what if there are many words?". Answer with a trie: one walk per start cell, following the trie, finds all the words together.
  • Expect "why 3^L and not 4^L?". After the first step, one of the four neighbors is the cell you came from. It is marked, so it fails at once and never branches.

Where frontend code uses it

The same idea in real UI code
  • Word games in the browser, such as letter-grid puzzles, check a typed word by searching neighboring tiles this way.
  • The "recursive backtracker" is a popular way to generate mazes for canvas games: walk to a random unvisited neighbor and step back when stuck.
  • Spreadsheet tools that trace a path through neighboring cells, such as a snake-like fill pattern, follow the same step-mark-unmark pattern.

Related algorithms