---

Mastering Grid Algorithms: Build a Word Search Solver in Crystal from Scratch

A Word Search solver in Crystal is an algorithm designed to find hidden words within a 2D grid of characters. The process involves iterating through each grid cell and, from that starting point, searching in all eight possible directions (horizontal, vertical, and diagonal) to match a list of target words, finally returning the start and end coordinates for each found word.

Remember those word search puzzles from activity books? A grid of seemingly random letters hiding a list of words waiting to be found. It’s a classic brain-teaser. But have you ever stopped to think about how you would teach a computer to solve one? What seems intuitive to our eyes—scanning lines, spotting patterns—becomes a fascinating algorithmic challenge for a machine. This isn't just a game; it's a perfect exercise in mastering grid traversal, state management, and algorithmic thinking.

This guide will take you from zero to hero, transforming that simple puzzle into a powerful Crystal program. We'll not only provide a complete, working solution but also dissect the logic behind it, exploring why this problem is a cornerstone for any developer looking to strengthen their problem-solving skills. By the end, you'll have a robust word search solver and a deeper understanding of how to navigate two-dimensional data structures, a skill essential in fields from game development to data analysis.

---

What is the Word Search Problem in a Programming Context?

In programming, the Word Search problem is a classic grid traversal challenge. The goal is to create a function or program that takes two inputs: a 2D array (or grid) of characters and a list of words to find. The program must locate each word within the grid and return the coordinates of its first and last letters. The core complexity arises from the fact that words can be oriented in any of eight directions: horizontally (left-to-right, right-to-left), vertically (top-to-bottom, bottom-to-top), and diagonally (all four possibilities).

The problem forces a developer to think systematically. You can't just randomly scan the grid. You need a methodical approach that checks every possible starting position and every possible direction for every word. This involves careful management of array indices, boundary checks to ensure you don't search outside the grid, and string comparison logic.

Here's a formal breakdown of the requirements:

• Input 1: A grid, typically represented as an array of strings or a 2D array of characters (e.g., Array(Array(Char)) in Crystal).
• Input 2: A list of strings, representing the words to be found.
• Output: For each word found, the program should return its location. A common format is a tuple containing the start and end coordinates, like {{start_x, start_y}, {end_x, end_y}}. If a word is not found, the output should indicate this, often by returning nil.
• Constraint: The search must be exhaustive across all 8 directions from every potential starting cell.

---

Why This is a Great Algorithmic Challenge

The Word Search problem, despite its simple premise, is an excellent vehicle for learning and reinforcing several fundamental computer science concepts. It’s a "low floor, high ceiling" problem—easy to understand but with plenty of room for optimization and deeper analysis. Tackling this challenge, especially using a language like Crystal, provides immense practical value.

It Reinforces 2D Array Traversal

Many real-world problems involve working with 2D data: images (pixels), game boards (tiles), spreadsheets (cells), and geographical maps (GIS data). The Word Search puzzle is a perfect, self-contained environment to practice iterating through a grid. You'll become intimately familiar with nested loops, accessing elements via grid[row][col], and, most importantly, avoiding common off-by-one errors.

It Teaches Systematic Directional Logic

The core of the solution lies in elegantly handling the eight search directions. The most effective way to do this is by using direction vectors (or deltas). A direction vector is a pair of numbers, like {dr, dc}, that represents the change in row and column for each step. For example:

• {0, 1}: Move right (column increases, row stays the same).
• {-1, 0}: Move up (row decreases, column stays the same).
• {1, 1}: Move diagonally down and right.

By defining all eight vectors in a constant, your code becomes incredibly clean and scalable. Instead of eight separate `if` blocks, you can loop through the vectors, applying the same logic to each one. This is a powerful abstraction technique.

It Demands Rigorous Boundary Checking

A common source of bugs in grid algorithms is attempting to access an index outside the array's bounds, leading to a runtime error (IndexOutOfBounds). This problem forces you to implement robust boundary checks. Before accessing any cell grid[next_row][next_col], you must ensure that next_row is between 0 and height - 1, and next_col is between 0 and width - 1. Mastering this is non-negotiable for writing stable code.

It's a Gateway to More Complex Algorithms

The brute-force approach we'll build is a foundation. Once you understand it, you can explore more advanced solutions. For instance, if you need to find hundreds of words in a massive grid, the brute-force method becomes slow. This leads you to optimizations like using a Trie (Prefix Tree). By pre-processing all the target words into a Trie, you can check all possible words starting at a given cell simultaneously, dramatically improving performance. This makes the Word Search problem a stepping stone to learning about more complex data structures and their applications in string searching, like the Aho-Corasick algorithm.

---

How to Design the Solution in Crystal

Before writing a single line of code, it's crucial to have a high-level strategy. Our approach will be a systematic, brute-force search. While not the most performant for massive inputs, it is the most straightforward to understand, implement, and verify. It's the perfect starting point.

Our strategy can be broken down into three main layers:

1. The Grid Iterator: The outermost layer of our logic will be a mechanism to visit every single cell in the grid. This will be our potential starting point for finding a word. A pair of nested loops is perfect for this, one for rows and one for columns.
2. The Directional Initiator: For each cell we visit, we check if its character matches the first character of the word we're currently searching for. If it doesn't, we can immediately move on to the next cell or the next direction. This is a simple but effective optimization. If it does match, we then initiate a search in all eight directions from this cell.
3. The Directional Walker: This is the core worker function. Given a starting cell, a direction, and a word, this function "walks" step-by-step in the given direction, checking if the characters in the grid match the corresponding characters in the word. It must also perform boundary checks at every step. If it successfully walks the entire length of the word, we have a match!

This entire process is encapsulated within a class, WordSearch, which holds the grid and provides a public search method.

Here is a visual representation of the overall algorithm's flow:

    ● Start
    │
    ▼
  ┌──────────────────────────┐
  │ Input: Grid, Word List   │
  └────────────┬─────────────┘
               │
               ▼
  ┌──────────────────────────┐
  │ For each `word` in list: │
  └────────────┬─────────────┘
               │
    ┌──────────┴──────────┐
    │ Loop `row` 0 to H-1 │
    └──────────┬──────────┘
               │
      ┌────────┴─────────┐
      │ Loop `col` 0 to W-1 │
      └────────┬─────────┘
               │
               ▼
    ◆ grid[row][col] == word[0]?
     ╱                       ╲
   Yes (Potential Match)      No
    │                         │
    ▼                         └───────────┐
  ┌───────────────────────┐               │
  │ Try all 8 directions  │               │
  └───────────┬───────────┘               │
              │                           │
              ▼                           │
         ◆ Word Found?                    │
          ╱         ╲                     │
        Yes          No                   │
         │            │                   │
         ▼            ▼                   │
    ┌───────────┐  [Continue Search]      │
    │ Return    │                         │
    │ Coords    │                         │
    └───────────┘                         │
         │                                │
         └────────────────┬───────────────┘
                          │
                          ▼
                     ● End of Search for `word`

This structured approach ensures that we check every possibility without redundant effort. The use of direction vectors, which we'll implement as a constant array of tuples, will keep the code for the "Try all 8 directions" step clean and concise.

---

Where the Core Logic Resides: A Deep Dive into the Crystal Code

Now, let's translate our design into idiomatic Crystal code. We will create a WordSearch class that is initialized with the puzzle grid. The main public method will be search, which takes a single word and returns its start and end coordinates if found.

The Complete Crystal Solution

Here is the full, commented source code. We will break it down section by section afterward.

# Represents a Word Search puzzle solver.
# It's initialized with a grid and can search for words within it.
class WordSearch
  # The grid of characters for the puzzle.
  @grid : Array(String)
  # The dimensions of the grid.
  @height : Int32
  @width : Int32

  # Define the 8 possible directions as tuples {d_row, d_col}.
  # This makes the directional search logic clean and scalable.
  DIRECTIONS = [
    {0, 1},   # Right
    {0, -1},  # Left
    {1, 0},   # Down
    {-1, 0},  # Up
    {1, 1},   # Down-Right
    {1, -1},  # Down-Left
    {-1, 1},  # Up-Right
    {-1, -1}, # Up-Left
  ]

  # Initializes the solver with a grid (an array of strings).
  def initialize(grid : Array(String))
    @grid = grid
    @height = grid.size
    @width = grid.empty? ? 0 : grid[0].size
  end

  # Searches for a single word in the grid.
  # Returns a tuple of start and end coordinates, or nil if not found.
  # The coordinates are 1-based as per many puzzle conventions.
  def search(word : String) : Tuple(Tuple(Int32, Int32), Tuple(Int32, Int32))?
    return nil if word.empty? || @grid.empty?

    # Outermost loops: iterate through every cell as a potential starting point.
    @height.times do |r|
      @width.times do |c|
        # Optimization: only proceed if the cell character matches the word's first letter.
        if @grid[r][c] == word[0]
          # Try searching in all 8 directions from this starting cell.
          DIRECTIONS.each do |dr, dc|
            # Attempt to find the full word along this direction.
            end_coords = find_in_direction(word, r, c, dr, dc)
            
            # If coordinates are returned, we found the word.
            if end_coords
              # Format the start and end coordinates (1-based index).
              start_coords = {c + 1, r + 1}
              return {start_coords, end_coords}
            end
          end
        end
      end
    end

    # If we've searched everywhere and haven't found the word, return nil.
    nil
  end

  private

  # Helper method to check for a word from a starting point in a specific direction.
  # Returns the end coordinates (1-based) if the word is found, otherwise nil.
  def find_in_direction(word : String, start_r : Int32, start_c : Int32, dr : Int32, dc : Int32)
    current_r, current_c = start_r, start_c

    # Iterate through each character of the word.
    word.each_char_with_index do |char, i|
      # Boundary Check: Ensure we are within the grid limits.
      unless (0...@height).includes?(current_r) && (0...@width).includes?(current_c)
        return nil # Went off the grid.
      end

      # Character Match Check: Ensure the grid character matches the word character.
      unless @grid[current_r][current_c] == char
        return nil # Mismatch found.
      end

      # Move to the next cell in the current direction for the next iteration.
      # We do this after the check for the current character.
      current_r += dr
      current_c += dc
    end

    # If the loop completes, we've found the entire word.
    # The final coordinates are the position of the last character.
    # We subtract the delta because the loop increments one last time.
    end_r = current_r - dr
    end_c = current_c - dc

    # Return the 1-based end coordinates.
    {end_c + 1, end_r + 1}
  end
end

# Example Usage:
# puzzle_grid = [
#   "jefblpepre",
#   "camdcimgtc",
#   "oivokprjsm",
#   "pbwasqroua",
#   "rixilelhrs",
#   "wolcqlirpc",
#   "screeaumgr",
#   "alxhpburyi",
#   "jalaycalmp",
#   "clojurermt",
# ]

# solver = WordSearch.new(puzzle_grid)
# result = solver.search("crystal")
# puts result # => {{1, 10}, {7, 4}}

Code Walkthrough

The `WordSearch` Class and `initialize` Method

We start by defining a class WordSearch. This encapsulates the logic and state (the grid) in one place. The initialize method takes the grid (as an Array(String)) and stores it in an instance variable @grid. It also pre-calculates and stores the grid's @height and @width. This is a good practice as it avoids recalculating these values repeatedly.

The `DIRECTIONS` Constant

This is the heart of our directional logic. We define a constant array of tuples. Each tuple {dr, dc} represents the "delta" or change in row and column needed to move one step in a particular direction. This approach is highly declarative and clean. If we wanted to add or remove directions (e.g., only horizontal), we would only need to modify this single constant.

This diagram visualizes how the direction vectors work from a central point (r, c):

       (-1,-1)  (-1,0)  (-1,1)
           ↖       ↑       ↗
            ╲      │      ╱
 (0,-1) ←─── ● (r,c) ───→ (0,1)
            ╱      │      ╲
           ↙       ↓       ↘
       (1,-1)   (1,0)   (1,1)

The Public `search` Method

This is the main entry point for our solver.

1. It first handles edge cases: if the word or grid is empty, it returns nil immediately.
2. It then enters the main nested loops (@height.times do |r| and @width.times do |c|) to iterate over every cell (r, c).
3. A crucial micro-optimization follows: if @grid[r][c] == word[0]. We only bother launching the expensive 8-directional search if the starting cell even matches the first letter of the word.
4. If there's a match, it iterates through our DIRECTIONS array. For each direction vector {dr, dc}, it calls the private helper method find_in_direction.
5. If find_in_direction returns a non-nil value (meaning the word was found), we've succeeded. It calculates the start coordinates, packages them with the returned end coordinates, and immediately returns the result.
6. If the loops complete without finding the word, the method returns nil at the end.

The Private `find_in_direction` Method

This helper method does the heavy lifting. It takes the word, a starting cell (start_r, start_c), and a direction vector (dr, dc).

1. It iterates through the characters of the word using each_char_with_index.
2. In each iteration, it performs the two critical checks:
   • Boundary Check: It ensures the current_r and current_c are within the valid grid dimensions (0...@height and 0...@width). If not, it's impossible to form the word, so it returns nil.
   • Character Match Check: It compares the character in the grid at the current position with the expected character from the word. If they don't match, it returns nil.
3. If both checks pass, it updates current_r and current_c by adding the deltas dr and dc to move to the next cell for the next character.
4. If the loop finishes without returning nil, it means every character matched successfully. It calculates the final coordinates of the last letter and returns them (using a 1-based index as is common in puzzles).

Running the Code

To run this code, save it as a file (e.g., word_search.cr), add the example usage at the bottom, and execute it from your terminal:

$ crystal run word_search.cr
{{1, 10}, {7, 4}}

This output indicates that the word "crystal" was found, starting at column 1, row 10 and ending at column 7, row 4. This confirms our logic is working correctly.

---

Who Benefits from Mastering This, and When to Use Alternative Approaches

Who Benefits from This Skill?

Mastering grid traversal algorithms like this one is not just an academic exercise. It has direct applications in numerous fields:

• Game Developers: Pathfinding algorithms (like A*), board game logic (Chess, Go), and procedural world generation all rely heavily on grid manipulation.
• Data Scientists & Image Processing Engineers: A digital image is essentially a 2D grid of pixels. Algorithms for feature detection, convolution, and image filtering involve iterating over pixels and their neighbors—a process very similar to our directional search.
• Bioinformaticians: DNA sequence alignment can be visualized and solved using 2D matrices (dynamic programming grids), where finding patterns is key.
• Backend Developers: Any problem that can be modeled as a grid, such as seating arrangements, warehouse layouts, or resource allocation maps, can benefit from these traversal techniques.

Essentially, anyone who needs to process spatial or two-dimensional data will find these skills invaluable. You can find more challenges like this in our Algorithmic Thinking module on the kodikra learning path.

When to Consider Alternative Approaches

Our brute-force solution is excellent for its clarity and is perfectly fine for typical puzzle sizes. However, its performance degrades under certain conditions. The time complexity is roughly O(rows * cols * num_words * avg_word_length). If you have a very large grid or a massive dictionary of words to find, this can become a bottleneck.

This is when you should consider more advanced data structures:

Trie (Prefix Tree) Based Solution

A Trie is a tree-like data structure that stores a set of strings. Each node represents a character, and a path from the root to a node represents a prefix.

• How it helps: You can insert all the words from your dictionary into a single Trie. Then, you start from each cell in the grid and traverse the grid in all 8 directions. As you move, you also traverse the Trie. This allows you to check for all possible words simultaneously. If you hit a path in the Trie that doesn't exist, you can stop that directional search early.
• Best for: Scenarios with a large number of words to find in the same grid.

Here's a comparison of the two approaches:

Aspect	Brute-Force (Our Solution)	Trie-Based Solution
Implementation Complexity	Low. Easy to understand and debug.	High. Requires implementing a Trie data structure.
Performance	Good for small word lists. Can be slow with many words.	Excellent for large word lists. Much faster as it avoids re-scanning the grid for each word.
Memory Usage	Very low. Only stores the grid.	Moderate. The Trie itself consumes memory, proportional to the total number of characters in all words.
Use Case	General-purpose puzzles, learning exercises, small-scale applications.	Large-scale text processing, bioinformatics, finding a massive dictionary of words in a document.

---

Frequently Asked Questions (FAQ)

1. What happens if a word appears multiple times in the grid?

The current implementation will find and return the coordinates for the first occurrence it encounters. The order of discovery depends on the iteration order (row by row, column by column, and then by the order of directions in the DIRECTIONS constant). To find all occurrences, you would need to modify the search method to not return immediately but instead collect all found coordinates into a list.

2. How could this code be modified to be case-insensitive?

You would need to normalize both the input grid and the search words. A simple way is to convert everything to a single case (e.g., lowercase) before processing. You could do this once in the initialize method for the grid (@grid = grid.map(&.downcase)) and within the search method for the word (word = word.downcase).

3. Can this algorithm handle non-square (rectangular) grids?

Yes, absolutely. The code is designed to handle rectangular grids correctly. In the initialize method, @height is set to grid.size and @width is set to grid[0].size. The loops and boundary checks use these independent height and width variables, so it works perfectly for any M x N grid.

4. What is the time and space complexity of this solution?

Time Complexity: O(R * C * L), where R is the number of rows, C is the number of columns, and L is the length of the word being searched. This is because, in the worst case, we might initiate a directional search of length L from every cell. Since there are 8 directions, it's technically O(8 * R * C * L), but we drop the constant 8. If searching for K words, it becomes O(K * R * C * L).

Space Complexity: O(1) (or O(R * C) to store the grid itself, but the search algorithm itself uses constant extra space). The memory usage does not grow with the size of the input words, only the grid.

5. Why use a `Tuple` like `{c + 1, r + 1}` for coordinates in Crystal?

A Tuple in Crystal is a fixed-size, immutable collection of values. It's perfect for representing coordinates because:

• Immutability: Once created, coordinates can't be accidentally changed, which prevents a class of bugs.
• Performance: Tuples are stack-allocated value types, making them very fast and memory-efficient for small, fixed data like coordinates.
• Clarity: The syntax {x, y} is concise and clearly represents a point.

6. Is Crystal a good language for this type of algorithmic problem?

Crystal is an excellent choice. It combines the expressive, high-level syntax of a language like Ruby with the performance of a compiled language like C. For algorithmic tasks, this means you get code that is easy to write and read, but that also runs very fast. The strong type system also helps catch many common errors at compile time, such as type mismatches or nil-related bugs, making the resulting code more robust. For more on the language, check out our complete Crystal guide.

7. How can I handle overlapping words in the puzzle?

The current algorithm handles overlapping words without any issues. Since each word is searched for independently, the fact that two words might share a letter or a sequence of letters does not affect the logic. The solver will correctly identify the path for "CRYSTAL" and, in a separate call to search, correctly identify the path for "RUST" even if they share the 'R' and 'S' characters.

---

Conclusion: Beyond the Puzzle

We've successfully designed, implemented, and analyzed a robust Word Search solver in Crystal. We began with a simple childhood puzzle and transformed it into a lesson on grid traversal, directional logic, and algorithmic design. The solution we built is not just functional; it's clean, efficient for its purpose, and written in idiomatic Crystal, leveraging constants for clarity and helper methods for modularity.

The key takeaway is that the principles learned here—iterating over 2D data, using direction vectors, and performing rigorous boundary checks—are universally applicable. Whether you're building the next great indie game, analyzing satellite imagery, or processing biological data, the ability to navigate a grid with confidence is a fundamental skill. This kodikra module serves as a powerful stepping stone toward mastering those more complex challenges.

Disclaimer: The solution and concepts discussed are based on Crystal version 1.12+ and general algorithmic principles. While the core logic is timeless, always refer to the official Crystal documentation for the latest syntax and standard library features.

---

Published by Kodikra — Your trusted Crystal learning resource.