intermediate6 min read·Updated October 3, 2026

Word Search on a Board Explained: Finding ABCCED in a 3×4 Matrix

Master matrix backtracking by tracing 'ABCCED' on a 3×4 board. Learn the mental model for state exploration, visited cell tracking, and edge cases.

By Learnisim AI·Published October 3, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Recursion basics
  • 2D arrays / matrices
  • Basic Graph DFS
Word Search Backtracking: Finding "ABCCED" on a 3x4 Grid 1. Board & Winning Path (A → B → C → C → E → D) A #1 (0,0) B #2 (0,1) C #3 (0,2) E S F C #4 (1,2) S A (alt start) D #6 (2,1) E #5 (2,2) E 2. DFS State Exploration & Backtracking Tree 'A' (0,0) 'B' (0,1) 'C' (0,2) 'C' (1,2) 'E' (2,2) 'D' (2,1) [FOUND!] Dead End If neighbor doesn't match remaining word suffix → Backtrack immediately Core Mechanics of Grid Backtracking 4-Directional Movement Steps connect only up, down, left, or right between adjacent cells. Diagonal steps are invalid! In-Place Visited Sentinel Temporarily overwrite board[r][c] with '#' to prevent cell reuse. Restore original letter on backtrack. Why Linear Scans Fail Words snake across rows & cols; flattening the 2D matrix into a string misses winding paths entirely.
Find "ABCCED" on [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] overview diagram
Why

Why simple string matching fails on a grid

Phase 1: The Grid Search Problem

Imagine you are handed a 3x4 character grid and asked whether the word "ABCCED" is hidden inside it.
Given the board:
json
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
If you treat the board like a flat book and read row by row, you see strings like ABCE, SFCS, and ADEE—none of which spell "ABCCED". Even if you flatten all twelve letters into a single string, "ABCCED" appears nowhere in a straight line. Yet, if you start at the top-left A, step right to B, step right to C, drop down to the next C, step left to E, and drop down to D, you trace an exact matching path through the grid.
Linear scans fail because letters in a word do not follow standard reading order; they snake up, down, left, and right across adjacent cells. Without a systematic way to explore 4-adjacent neighbors while keeping track of where you have already stepped, you cannot distinguish between a valid winding path and a random jumble of letters.
Why Linear String Matching Fails on a Grid Target word: "ABCCED" — letters snake across 4-directional grid neighbors, not a flat line. 1. Linear Scan (Book Reading Order) Treats grid as flat string: ABCE S FCS ADEE A B C E S F C S A D E E "ABCCED" Not Found! Why it fails: • Reading rows left-to-right misses vertical drops. • The second 'C' and 'E'/'D' are on lower rows. • Flattening destroys 2D adjacency context. Result: False Negative Requires backtracking & graph traversal instead. 2. Valid Grid Path (DFS / Backtracking) Snakes 4-directionally: Up, Down, Left, Right A 1: Start B 2: Right C 3: Right E S F C 4: Down S A D 6: Left (End) E 5: Down E Result: Match Found via Graph Traversal! Visited set prevents reusing cells in the same path. VS
Why simple string matching fails on a grid diagram
Model

The Grid As A Graph: Modeling Word Search As State Exploration

Phase 2: The Grid As A Graph

When searching for the word "ABCCED" on our board, we are not looking at a flat sequence of characters. Instead, every cell in the matrix acts as a node with up to four neighbors: up, down, left, and right. To match a word like "ABCCED", our mental model must shift from simple text searching to pathfinding. We need to find a sequence of connected cells such that the character in matches word[i], and no single cell is used more than once in the same path.
To build this model, consider how we step through our locked example. We begin at any cell containing "A". Looking at the board:
json
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
There are two "A" cells: board[0][0] and board[2][0]. Each "A" is a potential starting node. From a chosen start node, our search branches outward into a decision tree. At each depth of the tree, we check if any valid 4-adjacent neighbor matches word[i]. If a neighbor matches, we take that step deeper; if it does not, or if we hit a dead end, we must backtrack and try a different neighbor.
The Grid As A Graph: Word Search Pathfinding ("ABCCED") Modeling 2D matrix traversal as a state exploration graph with backtracking Board 3 × 4 Matrix A (0,0) B (0,1) C (0,2) E (0,3) S (1,0) F (1,1) C (1,2) S (1,3) A (2,0) D (2,1) E (2,2) E (2,3) 4-Way Adjacency (Up, Down, Left, Right) Each cell is a graph node. Edges exist only between adjacent cells. Target Word: A → B → C → C → E → D State Exploration & Decision Tree [0] A (0,0) [1] B (0,1) [2] C (0,2) [3] C (1,2) [4] E (2,2) [5] D (2,1) ✓ Dead End (S) Key Rules of Graph Exploration: • No cell reuse: Visited set tracks active path state. • Backtracking: Unmark visited cells on recursive return. • Multiple starts: Every 'A' cell triggers a fresh DFS search.
The Grid As A Graph: Modeling Word Search As State Exploration diagram
Worked example

Tracing the Word Search Path Step by Step

Phase 3: Walking Through the Grid

Now that we model the board as a graph where each cell connects to its four immediate neighbors, let us trace how the backtracking algorithm evaluates the target word "ABCCED" against our board.

Given and Setup

- Target word length:
- Start condition: Search for all cells containing the first letter A (). Looking at the board, A appears at (0, 0) and (2, 0).
- Expected Result: Return true because a valid adjacent path forms A → B → C → C → E → D.

Step-by-Step Trace

1. Scan for starting letter: We find A at (0, 0) and initiate our recursive DFS function search(0, 0, 0).
2. Match index 0: board[0][0] is 'A', which matches word[0]. We temporarily mutate board[0][0] to a sentinel like `
Phase 3: Tracing Start & First Match (A → B) Target word: "ABCCED" | Initiating search from start letter 'A' at (0, 0) A (0,0) B (0,1) C (0,2) E (0,3) S (1,0) F (1,1) C (1,2) S (1,3) A (2,0) D (2,1) E (2,2) E (2,3) DFS Execution State (Index 0 → 1) 1 Find Start Letter 'A' Found at (0, 0) and (2, 0). Begin at (0, 0). 2 Match Index 0 & Mutate board[0][0] matches word[0] ('A'). Temporarily mark board[0][0] as '#' (visited). 3 Explore 4 Neighbors Check Up, Down, Left, Right for word[1] ('B'). Neighbor (0, 1) contains 'B' → Valid Move! Recursive Call: search(row=0, col=1, index=1) Continuing path towards next target letter 'C' Active Cell (0,0) Matching word[0] = 'A' Next Target (0,1) Matching word[1] = 'B'
Tracing the Word Search Path Step by Step diagram
Practice

Predicting Backtracking and Visited States on a Variant

Phase 4:

Now that you have seen how the backtracking algorithm traces the path for ABCCED on our board, let us test your mental model on a modified scenario. Recall our board layout:
python
board = [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"]
]
Suppose we search for the shorter word "ABCB" using the exact same depth-first search and visited-marking strategy. During the exploration of path A B C, the algorithm arrives at the first C at coordinate . From there, it needs to find the letter B. The only adjacent unvisited cell containing B is the starting B at , but that cell is currently marked as visited ("#") in the current path stack.
Work through this step mentally: what happens when the algorithm attempts to revisit "B" while it is still active in the current recursion stack? Predict whether the search successfully matches "ABCB" or fails, and explain why cell state restoration alone does not prevent cell reuse within the same active path.
python
board = [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"]
]
word = "ABCB"
# Question: Does exist(board, word) return True or False? Explain the state of board[0][1] when the second 'B' is requested.
Apply

Applying Grid Pathfinding Patterns Beyond Simple Matrix Searches

Phase 5: Applying the Pattern

Now that you have seen how our locked example [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']] successfully validates `"ABCCED

FAQ

How does the algorithm find 'ABCCED' in the 3×4 board?
It starts at cell 'A' (0,0), moves right to 'B', then down to 'C', right to 'C', down to 'E', and down-left to 'D', successfully matching all characters without reusing any cell.
Why does simple string matching fail on a 2D grid?
Linear string matching assumes characters are contiguous in a single direction. A 2D grid allows movement in four directions (up, down, left, right), requiring a branching graph traversal rather than a single linear scan.
Why does searching for 'ABCB' return false on this board?
The backtracking algorithm prevents cell reuse within a single path. After matching A-B-C, the adjacent 'B' has already been visited in the current path, so it cannot be used again to complete 'ABCB'.
What is the time complexity of the word search algorithm?
In the worst case, the time complexity is O(N * M * 4^L), where N×M is the size of the board and L is the length of the word, due to exploring 4 possible directions at each step.

Keep learning