Grid word search by backtracking: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Try each starting cell, match the next letter through four orthogonal neighbors, and undo used-cell marks on a failed branch.

Try each grid cell as the first letter. Follow matching orthogonal neighbors while marking cells used by the current path. Undo a mark when a branch fails so later starting positions and branches can reuse the cell.

Open the 3D visualization

Grid word search by backtracking example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Grid word search by backtracking

Finding a small word in a letter grid without reusing a position.

Choosing an alternative

Maze DFS can permanently mark visited cells because reachability does not depend on the path prefix. Word search must undo used marks because feasibility depends on the remaining letters and current path.

Worked example: input and state changes

Example input

abce;sfcs;adee | abcced

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Try each cell; neighbors are up, right, down, left.

    State at this checkpoint
    {
      "values": [
        "a",
        "b",
        "c",
        "e",
        "s",
        "f",
        "c",
        "s",
        "a",
        "d",
        "e",
        "e"
      ],
      "active": [],
      "kind": "matrix",
      "columns": 4,
      "result": 0,
      "output": []
    }
  2. Step 2: Match b at cell 1.

    State at this checkpoint
    {
      "values": [
        "a:1",
        "b:2",
        "c",
        "e",
        "s",
        "f",
        "c",
        "s",
        "a",
        "d",
        "e",
        "e"
      ],
      "active": [
        1
      ],
      "kind": "matrix",
      "columns": 4,
      "result": 0,
      "output": []
    }
  3. Step 4: Match c at cell 6.

    State at this checkpoint
    {
      "values": [
        "a:1",
        "b:2",
        "c:3",
        "e",
        "s",
        "f",
        "c:4",
        "s",
        "a",
        "d",
        "e",
        "e"
      ],
      "active": [
        6
      ],
      "kind": "matrix",
      "columns": 4,
      "result": 0,
      "output": []
    }
  4. Step 5: Match e at cell 10.

    State at this checkpoint
    {
      "values": [
        "a:1",
        "b:2",
        "c:3",
        "e",
        "s",
        "f",
        "c:4",
        "s",
        "a",
        "d",
        "e:5",
        "e"
      ],
      "active": [
        10
      ],
      "kind": "matrix",
      "columns": 4,
      "result": 0,
      "output": []
    }
  5. Step 7: Found abcced along cells 0,1,2,6,10,9.

    State at this checkpoint
    {
      "values": [
        "a:1",
        "b:2",
        "c:3",
        "e",
        "s",
        "f",
        "c:4",
        "s",
        "a",
        "d:6",
        "e:5",
        "e"
      ],
      "active": [],
      "kind": "matrix",
      "columns": 4,
      "result": 1,
      "output": [
        0,
        1,
        2,
        6,
        10,
        9
      ]
    }

Expected final state

Found abcced along cells 0,1,2,6,10,9.

Complexity and input bounds

Family: Backtracking. Time complexity: O(rows * columns * 3^word length) bounded.

Implementation detail: The grid has at most four rows and columns and words have at most eight lowercase letters. Neighbor order is up, right, down, left. A cell label suffix shows its position in the current match. Downloads accept ASCII codes and return the first DFS path; an empty download word succeeds without output.

Space complexity: O(grid cells + word length) traversal state, plus returned path and saved frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..4 by 1..4 lowercase letter grid, rows separated by ; | word of 1..8 letters. A cell cannot be reused.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

A repeated letter requires distinct cells. Do not step diagonally or wrap across row boundaries. Restore used-cell state on every failed branch.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// rows/cols 1..4, lowercase ASCII integer grid and word codes 97..122, word length n 0..8. Orthogonal neighbors up, right, down, left; no cell reuse. Returns 1 and writes n flattened cell indices for the first DFS match, or 0 if absent (output unspecified). Output capacity at least n. Empty word succeeds without writing. O(rows*cols*3^n) bounded search, O(rows*cols+n) scratch. Input arrays unchanged. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(grid, rows, cols, word, n, output) {
    if (n == 0) { return 1; }
    let cells = rows*cols; if (n > cells) { return 0; }
    let stack = Array(256).fill(0); let next = Array(256).fill(0); let used = Array(256).fill(0); let depth = 0; let vertex = 0; let direction = 0; let candidate = 0;
    for (let start = 0; start < cells; start++) { if (grid[start] == word[0]) { depth = 0; stack[0] = start; next[0] = 0; used[start] = 1;
     while (depth >= 0) { vertex = stack[depth]; if (depth == n-1) { for (let i = 0; i < n; i++) { output[i] = stack[i]; } return 1; }
     if (next[depth] == 4) { used[vertex] = 0; depth--; } else { direction = next[depth]; next[depth]++; candidate = -1; if (direction == 0) { if (vertex >= cols) { candidate = vertex-cols; } } else { if (direction == 1) { if (vertex%cols+1 < cols) { candidate = vertex+1; } } else { if (direction == 2) { if (vertex+cols < cells) { candidate = vertex+cols; } } else { if (vertex%cols > 0) { candidate = vertex-1; } } } } if (candidate >= 0 && used[candidate] == 0 && grid[candidate] == word[depth+1]) { used[candidate] = 1; depth++; stack[depth] = candidate; next[depth] = 0; } }
     }
     } }
    return 0;
}

Source

Related primary research on backtrack programs. This is a source for the search method, not an asserted original word-search puzzle paper.