---

C# Word Search: From Zero to Grid-Traversing Hero

Solving a word search puzzle in C# is a classic algorithm challenge that involves iterating through each cell of a 2D character grid. For each cell, the algorithm checks all eight possible directions (horizontal, vertical, and diagonal) to determine if a target word originates there, returning the start and end coordinates upon a successful match.

Remember the satisfaction of circling a hidden word in a puzzle book? That simple joy masks a surprisingly complex logical challenge, especially when you try to teach a computer to do it. You're not just looking for letters; you're tracing paths, checking boundaries, and managing multiple possibilities at once. Many developers hit a wall when trying to translate this human intuition into robust C# code, getting lost in a maze of nested loops and confusing coordinate logic.

This guide will transform that confusion into clarity. We will dissect the word search problem, architect a clean and efficient C# solution from the ground up, and walk through every line of code. You'll master grid traversal, learn the power of directional vectors, and build a solver that can conquer any puzzle, leaving you with a deep understanding of 2D array manipulation and algorithmic thinking.

---

What is the Word Search Problem in C#?

The Word Search problem, a staple in the kodikra learning path for C#, presents a simple objective with a complex implementation. You are given two inputs: a grid of characters (often a square, but not necessarily) and a list of words to find within that grid.

The core task is to locate each word from the list inside the grid. A word can be oriented in any of eight directions:

• Horizontally (left-to-right and right-to-left)
• Vertically (top-to-bottom and bottom-to-top)
• Diagonally (top-left to bottom-right, bottom-right to top-left, top-right to bottom-left, and bottom-left to top-right)

For each word found, the program must return the starting and ending coordinates of that word within the grid. If a word is not found, this should be indicated accordingly. This challenge is less about complex data structures and more about meticulous logic, boundary checks, and systematic searching.

Why This is a Foundational Algorithm Challenge

The word search puzzle is more than just a game; it's a perfect exercise for honing fundamental programming skills. It forces you to think spatially and algorithmically. Mastering it demonstrates proficiency in:

• 2D Array/Grid Traversal: Systematically visiting every element in a two-dimensional data structure is a core skill used in image processing, game development (maps, boards), and data analysis.
• State Management: You need to keep track of the current position (row, column), the current direction you're searching in, and the current character of the word you're matching.
• Boundary Checking: A significant part of the logic involves ensuring your search doesn't go "out of bounds" of the grid. This is crucial for preventing IndexOutOfRangeException errors and writing robust code.
• Algorithmic Decomposition: Breaking a large problem ("find all words") into smaller, manageable sub-problems ("check one cell," "check one direction from this cell") is the essence of software engineering.

By solving this, you build a mental model for a whole class of problems involving pattern matching and grid exploration, which are common in technical interviews and real-world applications.

---

How to Design and Implement the Word Search Solver

Our approach will be a systematic, brute-force search. While highly optimized solutions exist for massive grids and dictionaries (like using a Trie), the brute-force method is the most intuitive, readable, and perfectly sufficient for typical puzzle sizes. It's the ideal starting point for understanding the core mechanics.

The overall logic follows a clear, hierarchical flow:

● Start with Puzzle & Word List
│
▼
┌───────────────────────────┐
│ Iterate through each WORD │
│ in the word list          │
└────────────┬──────────────┘
             │
             ▼
    ┌────────────────────┐
    │ Iterate through each CELL │
    │ (row, col) in the grid    │
    └──────────┬─────────┘
               │
               ▼
        ┌───────────────────────┐
        │ Iterate through all 8 DIRECTIONS │
        │ (dx, dy) vectors      │
        └──────────┬────────────┘
                   │
                   ▼
            ◆ Does cell char match
            │   first char of word?
            ╱                       ╲
          Yes                       No
           │                         │
           ▼                         └─────(Continue to next direction/cell)
    ┌────────────────────┐
    │ Trace full word path │
    │ in current direction │
    └──────────┬─────────┘
               │
               ▼
          ◆ Is the full
          │  word found?
          ╱             ╲
        Yes             No
         │               │
         ▼               └───────(Continue to next direction)
┌─────────────────────────┐
│ Record Start/End Coords │
│ & Move to next word     │
└──────────┬──────────────┘
           │
           ▼
      ● End of Search

This flowchart breaks the problem down into three nested loops: one for the words, one for the grid rows/columns, and one for the directions. This structure ensures we check every possible starting point for every word in every possible direction.

Step 1: Setting Up the C# Class and Data Structures

First, let's define our class structure. We'll have a WordSearch class that takes the puzzle grid in its constructor. The main public method will be Search, which takes the list of words to find.

We need a way to represent the 8 directions. A clean way to do this is with an array of tuples or a simple struct representing the change in `x` (column) and `y` (row) for each step. We'll call these `(dx, dy)` vectors.

    (dx, dy)
     ▲
     │
(-1, 1)  (-1, 0)  (-1, -1)
     ╲       │       ╱
      ●───────●───────●
(0, 1)│ (0, 0)│(0, -1) │ (x, y)
      ●───────●───────●
     ╱       │       ╲
(1, 1)   (1, 0)   (1, -1)

This diagram shows how each direction corresponds to a change in coordinates. For example, moving "down" means incrementing the row index (`y`) by 1 while the column index (`x`) stays the same, hence the vector `(1, 0)` (if we consider row as `y`). Let's clarify our coordinate system: `(row, col)`.

• Right: `(dx, dy) = (0, 1)` (col increases)
• Left: `(dx, dy) = (0, -1)` (col decreases)
• Down: `(dx, dy) = (1, 0)` (row increases)
• Up: `(dx, dy) = (-1, 0)` (row decreases)
• Down-Right: `(dx, dy) = (1, 1)`
• Up-Left: `(dx, dy) = (-1, -1)`
• Down-Left: `(dx, dy) = (1, -1)`
• Up-Right: `(dx, dy) = (-1, 1)`

Step 2: The Complete C# Solution Code

Here is the full, commented source code for the WordSearch solver. This implementation is designed for clarity and correctness, following the logic we've outlined. The coordinate system used in the output is 1-based, as is common in puzzle descriptions, while the internal logic is 0-based for array indexing.

using System;
using System.Collections.Generic;

public class WordSearch
{
    private readonly string[] _puzzle;
    private readonly int _rowCount;
    private readonly int _colCount;

    // Define the 8 directional vectors (row_delta, col_delta)
    private static readonly (int dr, int dc)[] Directions =
    {
        (0, 1),   // Right
        (0, -1),  // Left
        (1, 0),   // Down
        (-1, 0),  // Up
        (1, 1),   // Down-Right
        (-1, -1), // Up-Left
        (1, -1),  // Down-Left
        (-1, 1)   // Up-Right
    };

    public WordSearch(string puzzle)
    {
        // Split the puzzle string into an array of strings (rows)
        _puzzle = puzzle.Split('\n');
        _rowCount = _puzzle.Length;
        _colCount = _rowCount > 0 ? _puzzle[0].Length : 0;
    }

    // The main search method
    public Dictionary<string, ((int, int), (int, int))?> Find(string[] wordsToSearchFor)
    {
        var results = new Dictionary<string, ((int, int), (int, int))?>();

        foreach (var word in wordsToSearchFor)
        {
            results[word] = FindWord(word);
        }

        return results;
    }

    // Helper method to find a single word
    private ((int, int), (int, int))? FindWord(string word)
    {
        if (string.IsNullOrEmpty(word))
        {
            return null;
        }

        // Iterate through every cell in the grid as a potential starting point
        for (int r = 0; r < _rowCount; r++)
        {
            for (int c = 0; c < _colCount; c++)
            {
                // Check if the character at this cell matches the first letter of the word
                if (_puzzle[r][c] == word[0])
                {
                    // If it matches, check all 8 directions from this cell
                    foreach (var dir in Directions)
                    {
                        var endCoords = TraceWordInDirection(word, r, c, dir);
                        if (endCoords.HasValue)
                        {
                            // Word found! Return 1-based coordinates.
                            // Start: (c+1, r+1), End: (end_col+1, end_row+1)
                            return (((c + 1, r + 1)), (endCoords.Value.endCol + 1, endCoords.Value.endRow + 1));
                        }
                    }
                }
            }
        }

        // If we finish all loops and haven't found the word, it's not in the puzzle
        return null;
    }
    
    // Traces a word from a starting point in a specific direction
    private (int endRow, int endCol)? TraceWordInDirection(string word, int startRow, int startCol, (int dr, int dc) direction)
    {
        int currentRow = startRow;
        int currentCol = startCol;

        // Iterate through the characters of the word
        for (int i = 0; i < word.Length; i++)
        {
            // Boundary check: ensure we are within the grid
            if (currentRow < 0 || currentRow >= _rowCount || currentCol < 0 || currentCol >= _colCount)
            {
                return null; // Went off the grid
            }

            // Character check: ensure the grid character matches the word character
            if (_puzzle[currentRow][currentCol] != word[i])
            {
                return null; // Mismatch found
            }
            
            // If this is the last character of the word, we have a full match
            if (i == word.Length - 1)
            {
                return (currentRow, currentCol);
            }

            // Move to the next cell in the given direction
            currentRow += direction.dr;
            currentCol += direction.dc;
        }

        return null; // Should not be reached, but good for completeness
    }
}

Step 3: Detailed Code Walkthrough

Let's break down the logic of the solution piece by piece to understand exactly how it works.

The `WordSearch` Class and Constructor

The class stores the puzzle grid (_puzzle) as an array of strings. The constructor takes a single multi-line string and splits it by the newline character `\n` to create this array. It also pre-calculates the row and column counts for efficiency, preventing repeated calculations later.

The `Directions` Array

The static readonly (int dr, int dc)[] Directions array is the heart of the traversal logic. It's a constant collection of tuples, where each tuple represents a vector. dr is the "delta row" (change in row index) and dc is the "delta column". This array makes the code clean and extensible; if you wanted to support only horizontal and vertical searches, you would simply remove the diagonal vectors.

The `Find` Method

This is the public entry point. It initializes a Dictionary to store the results. It then iterates through each word in the input array wordsToSearchFor and calls the private helper method FindWord for each one. The result (either the coordinate tuple or null) is stored in the dictionary.

The `FindWord` Method (The Core Loop)

This is where the main search logic resides.

1. Outer Loops: Two nested for loops iterate over every single cell (r, c) of the grid. This ensures that we consider every possible starting position for the word.
2. First Character Match: Inside the loops, an if statement provides a quick optimization. It checks if the character at the current grid cell _puzzle[r][c] matches the first character of the word. If it doesn't, there's no point in checking any directions from this cell for this word, so we continue to the next cell.
3. Directional Loop: If the first character matches, we then loop through our Directions array. For each of the 8 directions, we call TraceWordInDirection.
4. Result Handling: If TraceWordInDirection returns a non-null value, it means the entire word was found. We then construct the final result tuple, converting the 0-based internal indices to 1-based coordinates for the output, and return immediately. The problem statement implies we only need the first occurrence.
5. Not Found: If the loops complete without finding the word, the method returns null.

The `TraceWordInDirection` Method

This helper function does the heavy lifting of checking a single path.

1. Initialization: It takes the word, a starting cell (startRow, startCol), and a direction vector.
2. Character Loop: It iterates from the first to the last character of the word.
3. Boundary Check: In each iteration, it first checks if the currentRow and currentCol are still within the grid's bounds. If not, the path is invalid, and it returns null.
4. Character Check: It then compares the character in the grid at the current position with the corresponding character in the word. If they don't match, the path is broken, and it returns null.
5. Successful Match: If the loop successfully reaches the last character of the word and it matches, we've found the complete word. The method returns the current coordinates, which are the end coordinates of the word.
6. Advancement: After a successful character match (that isn't the last one), it updates currentRow and currentCol by adding the directional deltas dr and dc, effectively taking one step along the path.

This layered approach, with helper methods handling specific responsibilities, makes the code readable, testable, and easy to debug.

---

Alternative Approaches and Performance Considerations

The brute-force method is excellent for its simplicity. However, it's worth understanding its performance characteristics and potential alternatives for very large-scale problems.

Algorithmic Complexity

Let's analyze the time complexity of our solution. Let:

• W be the number of words to find.
• R be the number of rows in the grid.
• C be the number of columns in the grid.
• L be the length of the longest word.

The complexity is roughly O(W * R * C * L). This is because for each word (W), we potentially scan every cell (R * C), and from each cell, we trace in 8 directions for the length of the word (L). The 8 directions are a constant factor, so they don't change the overall Big O notation.

For most puzzles, this is perfectly acceptable. But if you had a 1000x1000 grid and a dictionary of 100,000 words, this approach would be too slow.

Optimized Approach: Using a Trie (Prefix Tree)

A more advanced solution involves using a Trie data structure. A Trie is a tree-like structure perfect for storing a dictionary of words that allows for very fast prefix lookups.

The logic would be inverted: 1. Build the Trie: Insert all the words you need to find into the Trie. 2. Scan the Grid: Iterate through each cell (r, c) of the grid. 3. Traverse from Each Cell: From each cell, start a recursive search (like a Depth First Search) in all 8 directions. As you traverse the grid, you simultaneously traverse the Trie. 4. Match and Prune: If the path you're taking in the grid (e.g., 'c', 'a', 't') corresponds to a valid path in the Trie, you continue. If at any point the next character in the grid path doesn't correspond to a child node in the Trie, you can immediately stop searching that path (pruning). If you reach a node in the Trie that marks the end of a word, you've found a match.

This approach changes the complexity because you are no longer searching for one word at a time. You are effectively searching for all words simultaneously.

Pros and Cons Comparison

Aspect	Brute-Force (Our Solution)	Trie-Based Approach
Implementation Complexity	Low. Easy to understand and debug. Uses basic loops and arrays.	High. Requires implementing a Trie and a recursive DFS-style search.
Performance	Good for small-to-medium puzzles. Becomes slow with many words or very large grids.	Excellent. Significantly faster for large word lists as it avoids re-scanning the grid for each word.
Memory Usage	Very low. Only stores the grid and word list.	Moderate to High. The Trie itself consumes memory, proportional to the total number of characters in all words.
Best Use Case	Coding challenges, interviews, typical application scenarios as seen in the kodikra C# curriculum.	Large-scale pattern matching, bioinformatics, spell-checkers with huge dictionaries.

---

Frequently Asked Questions (FAQ)

What is the time complexity of this word search algorithm?

The time complexity is approximately O(W * R * C * L), where W is the number of words, R and C are the dimensions of the grid, and L is the length of the longest word. This is because we iterate through each word, then each cell, and then trace the word's length.

How can this solution handle case-insensitivity?

To make the search case-insensitive, you can convert both the grid characters and the search words to a consistent case (e.g., lowercase) before performing comparisons. You could do this by creating a temporary lowercase version of the grid or by calling ToLower() on characters during the check, though the former is more efficient if done once upfront.

What happens if a word appears multiple times in the puzzle?

The current implementation is designed to find and return the first occurrence of a word it encounters. The loops are structured to stop and return as soon as a full match is confirmed by TraceWordInDirection. To find all occurrences, you would need to modify the logic to not return immediately, but instead store the found coordinates in a list and continue searching from the next cell.

Can this logic be adapted for non-square (rectangular) grids?

Yes, absolutely. The code is already robust enough to handle rectangular grids. The constructor correctly captures _rowCount and _colCount independently. The boundary checks inside TraceWordInDirection use these distinct variables (currentRow < _rowCount and currentCol < _colCount), ensuring the search never goes out of bounds, regardless of the grid's aspect ratio.

What are the common ways to represent coordinates in C#?

There are several good options. Our solution uses tuples like (int, int), which are lightweight and convenient. For more complex scenarios, you could use the System.Drawing.Point struct, which provides named properties (X, Y). Alternatively, you could define your own custom struct Coordinate { public int Row; public int Col; } for maximum clarity and type safety.

What are some critical edge cases to test for this problem?

Good testing is key. You should always check for:

• An empty grid or an empty list of words.
• Words that are not present in the grid.
• Words that are a single character long.
• Words that start at the edge or corners of the grid.
• Puzzles where words overlap.

Our code handles these cases gracefully.

---

Conclusion: Beyond the Puzzle

You've successfully built a complete, robust word search solver in C#. This journey has taken you through the fundamentals of grid traversal, the elegance of directional vectors, and the importance of structured, algorithmic thinking. The techniques you've learned here—breaking down a problem, managing coordinates, and performing systematic boundary checks—are not just for puzzles. They are directly applicable to a wide range of programming domains, from game development to data visualization.

By working through this challenge from the exclusive kodikra.com C# learning path, you've added a powerful tool to your problem-solving arsenal. The key takeaway is the process: observing a problem, devising a step-by-step logical plan, and translating that plan into clean, efficient code. Keep practicing these skills, and you'll be well-equipped to tackle even more complex challenges ahead.

Technology Disclaimer: The C# code and concepts in this article are based on modern .NET (6+) and C# 10+ features, such as file-scoped namespaces and tuple syntax. The logic is fundamental and adaptable to older versions, but the syntax is contemporary. For a deeper dive into the language, explore our complete C# guide.

---

Published by Kodikra — Your trusted Csharp learning resource.