Word Search in Grid Using Backtracking in DSA Go - Build from Scratch

Word Search in Grid Using Backtracking

📖 Scenario: You are building a simple word search puzzle solver. The puzzle is a grid of letters, and you want to find if a given word exists in the grid by moving horizontally or vertically from one letter to the next.This is like searching for a hidden word in a crossword puzzle.

🎯 Goal: Build a program that checks if a given word can be found in the letter grid by moving up, down, left, or right without revisiting the same cell.

📋 What You'll Learn

Create a 2D slice of bytes called board with exact letters

Create a string variable called word with the exact value

Implement a backtracking function called exist that returns true if the word is found

Print true or false depending on whether the word exists in the grid

💡 Why This Matters

🌍 Real World

Word search puzzles and games use similar backtracking techniques to find words hidden in grids.

💼 Career

Backtracking algorithms are important in solving puzzles, pathfinding problems, and constraint satisfaction tasks in software development.

1

Create the letter grid

Create a 2D slice of bytes called board with these exact rows: {'A','B','C','E'}, {'S','F','C','S'}, {'A','D','E','E'}

DSA Go

// Create the 2D slice of bytes called board
// Your code here

Hint

Use a slice of byte slices to represent the grid. Each inner slice is a row of letters.

2

Set the word to search

Create a string variable called word and set it to the exact value "ABCCED"

DSA Go

package main

func main() {
    board := [][]byte{
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'},
    }
    // Create the string variable word
    // Your code here
}

Hint

Use a simple string variable to hold the word you want to find.

3

Implement the backtracking search function

Write a function called exist that takes board [][]byte and word string and returns bool. Use backtracking to check if the word exists in the grid by moving up, down, left, or right without revisiting cells. Call exist(board, word) inside main and store the result in a variable called found.

DSA Go

package main

func exist(board [][]byte, word string) bool {
    // Your code here
}

func main() {
    board := [][]byte{
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'},
    }
    word := "ABCCED"
    // Call exist and store result in found
    // Your code here
}

Hint

Use a helper function inside exist to try all directions recursively. Mark cells visited to avoid reuse.

4

Print the result

Print the value of the variable found using fmt.Println(found).

DSA Go

package main

func exist(board [][]byte, word string) bool {
    rows := len(board)
    cols := len(board[0])
    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    var backtrack func(r, c, index int) bool
    backtrack = func(r, c, index int) bool {
        if index == len(word) {
            return true
        }
        if r = rows || c = cols || visited[r][c] || board[r][c] != word[index] {
            return false
        }

        visited[r][c] = true

        if backtrack(r+1, c, index+1) || backtrack(r-1, c, index+1) || backtrack(r, c+1, index+1) || backtrack(r, c-1, index+1) {
            return true
        }

        visited[r][c] = false
        return false
    }

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if backtrack(r, c, 0) {
                return true
            }
        }
    }
    return false
}

func main() {
    board := [][]byte{
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'},
    }
    word := "ABCCED"
    found := exist(board, word)
    // Print found
    // Your code here
}

Hint

Use fmt.Println(found) to show if the word was found.

Practice

1. What is the main purpose of using backtracking in a word search grid problem?

easy

A. To count the number of words in the grid

B. To sort the grid alphabetically

C. To explore all possible paths to find the word

D. To replace characters in the grid

Solution

1. Step 1: Understand backtracking in word search

   Backtracking tries all possible paths in the grid to find the target word by exploring neighbors recursively.

2. Step 2: Eliminate other options

   Sorting, counting, or replacing characters are unrelated to the search process using backtracking.

3. Final Answer:

   To explore all possible paths to find the word -> Option C

4. Quick Check:

   Backtracking = Explore paths [OK]

Hint: Backtracking means trying all paths until word found [OK]

Common Mistakes:

• Thinking backtracking sorts or modifies the grid
• Confusing backtracking with simple iteration
• Assuming backtracking counts words directly

2. Which of the following is the correct way to check if a position (row, col) is inside the grid in Go?

easy

A. if row > 0 && row <= len(grid) && col > 0 && col <= len(grid[0])

B. if row > 0 && row < len(grid) && col > 0 && col < len(grid[0])

C. if row >= 0 && row <= len(grid) && col >= 0 && col <= len(grid[0])

D. if row >= 0 && row < len(grid) && col >= 0 && col < len(grid[0])

Solution

1. Step 1: Understand grid indexing in Go

   Grid indices start at 0 and go up to length-1, so valid indices satisfy 0 <= row < len(grid) and 0 <= col < len(grid[0]).

2. Step 2: Check each option

   if row >= 0 && row < len(grid) && col >= 0 && col < len(grid[0]) correctly uses >= 0 and < length. Options A, C, D use incorrect bounds like > 0 or <= length which are off by one.

3. Final Answer:

   if row >= 0 && row < len(grid) && col >= 0 && col < len(grid[0]) -> Option D

4. Quick Check:

   Index check = if row >= 0 && row < len(grid) && col >= 0 && col < len(grid[0]) [OK]

Hint: Use zero-based indexing with < length for bounds [OK]

Common Mistakes:

• Using > 0 instead of >= 0 excludes first row/column
• Using <= length allows out-of-range index
• Confusing row and column lengths

3. What will be the output of the following Go code snippet for word search?

grid := [][]byte{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}}
word := "ABCCED"
found := exist(grid, word)
fmt.Println(found)

func exist(board [][]byte, word string) bool {
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            if backtrack(board, word, i, j, 0) {
                return true
            }
        }
    }
    return false
}

func backtrack(board [][]byte, word string, row, col, index int) bool {
    if index == len(word) {
        return true
    }
    if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) || board[row][col] != word[index] {
        return false
    }
    temp := board[row][col]
    board[row][col] = '#'
    found := backtrack(board, word, row+1, col, index+1) ||
             backtrack(board, word, row-1, col, index+1) ||
             backtrack(board, word, row, col+1, index+1) ||
             backtrack(board, word, row, col-1, index+1)
    board[row][col] = temp
    return found
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Understand the grid and word

   The grid contains the letters to form the word "ABCCED" starting at (0,0) moving right and down.

2. Step 2: Trace backtracking calls

   Backtracking explores neighbors and marks visited cells with '#'. The word "ABCCED" can be found following the path A->B->C->C->E->D.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Word found = true [OK]

Hint: Trace path letter by letter with backtracking [OK]

Common Mistakes:

• Not marking visited cells causing revisits
• Incorrect boundary checks causing false negatives
• Assuming word is not found without tracing path

4. The following Go code for word search returns false even when the word exists. What is the bug?

func backtrack(board [][]byte, word string, row, col, index int) bool {
    if index == len(word) {
        return true
    }
    if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) || board[row][col] != word[index] {
        return false
    }
    // Missing marking visited cell
    found := backtrack(board, word, row+1, col, index+1) ||
             backtrack(board, word, row-1, col, index+1) ||
             backtrack(board, word, row, col+1, index+1) ||
             backtrack(board, word, row, col-1, index+1)
    return found
}

medium

A. The function does not mark visited cells, causing revisits

B. The base case is incorrect and should return false

C. The boundary checks are missing

D. The word parameter is not passed correctly

Solution

1. Step 1: Analyze the backtrack function

   The function checks boundaries and matches characters but does not mark visited cells, so it can revisit the same cell multiple times.

2. Step 2: Understand the impact of missing visited marking

   Without marking visited cells, the search may loop or fail to find the word correctly because it revisits cells already used in the current path.

3. Final Answer:

   The function does not mark visited cells, causing revisits -> Option A

4. Quick Check:

   Missing visited marking = The function does not mark visited cells, causing revisits [OK]

Hint: Always mark visited cells to avoid revisiting [OK]

Common Mistakes:

• Ignoring visited marking causes infinite loops
• Misunderstanding base case logic
• Assuming boundary checks fix revisits

5. Given a grid and a list of words, how can you efficiently find all words present in the grid using backtracking? Choose the best approach.

hard

A. Run backtracking separately for each word on the entire grid

B. Build a Trie of words and use backtracking with pruning to find all words

C. Sort the grid and words alphabetically before searching

D. Replace all grid letters with '#' and then search

Solution

1. Step 1: Understand the problem of multiple words

   Searching each word separately is inefficient because it repeats similar searches multiple times.

2. Step 2: Use Trie with backtracking

   Building a Trie (prefix tree) of all words allows pruning paths early if no word matches, improving efficiency significantly.

3. Step 3: Eliminate incorrect options

   Sorting or replacing letters does not help search. Running backtracking separately is slow.

4. Final Answer:

   Build a Trie of words and use backtracking with pruning to find all words -> Option B

5. Quick Check:

   Trie + backtracking = efficient multi-word search [OK]

Hint: Use Trie to prune backtracking paths for multiple words [OK]

Common Mistakes:

• Searching each word independently wastes time
• Ignoring Trie data structure benefits
• Trying to sort grid which doesn't help search