How do I search a two dimensional array in any direction

Question

I'm writing a word search puzzle in C# and I would like to be able to search the two dimensional array of characters for the words in an elegant manner.

The basic searches left to right, top to bottom etc, are not to difficult to write, however things start getting a little verbose when searching diagonally accross the array. I've got it working but I'm sure there's a better solution out there.

Here's an example of a puzzle I'm trying to solve, any ideas would be greatly appreciated.

BXXD
AXEX
TRXX
FXXX

BAT FRED

EDIT: Kudos to Steve for giving me the idea of searching compass points

EDIT: The result of the search needs to return the x1, y1 and x2, y2 co-ordinates of the words within the array.

EDIT: Thanks to Antti for providing a good algorithm for searching the array.

This the final result I came up with. I've based it on the algorithm in Antti's answer, having modified it to return the array offsets for the beginning and the end of any words found. This algorithm is going to be used a Word Search game I'm writing in WPF, for my kids. Thanks to everyone for helping me along. I'll post a link here to the app when it's respectable.

public class Range
{
    public Range(Coordinate start, Coordinate end)
    {
        Start = start;
        End = end;
    }

    public Coordinate Start { get; set; }
    public Coordinate End { get; set; }
}

public class Coordinate
{
    public Coordinate(int x, int y)
    {
        X = x;
        Y = y;
    }

    public int X { get; set; }
    public int Y { get; set; }
}

public class WordSearcher 
{
    public WordSearcher(char[,] puzzle)
    {
        Puzzle = puzzle;
    }

    public char[,] Puzzle { get; set; }

    // represents the array offsets for each
    // character surrounding the current one
    private Coordinate[] directions = 
    {
        new Coordinate(-1, 0), // West
        new Coordinate(-1,-1), // North West
        new Coordinate(0, -1), // North
        new Coordinate(1, -1), // North East
        new Coordinate(1, 0),  // East
        new Coordinate(1, 1),  // South East
        new Coordinate(0, 1),  // South
        new Coordinate(-1, 1)  // South West
    };

    public Range Search(string word)
    {
        // scan the puzzle line by line
        for (int y = 0; y < Puzzle.GetLength(0); y++)
        {
            for (int x = 0; x < Puzzle.GetLength(1); x++)
            {
                if (Puzzle[y, x] == word[0])
                {
                    // and when we find a character that matches 
                    // the start of the word, scan in each direction 
                    // around it looking for the rest of the word
                    var start = new Coordinate(x, y);
                    var end = SearchEachDirection(word, x, y);
                    if (end != null)
                    {
                        return new Range(start, end);
                    }
                }
            }
        }
        return null;
    }

    private Coordinate SearchEachDirection(string word, int x, int y)
    {
        char[] chars = word.ToCharArray();
        for (int direction = 0; direction < 8; direction++)
        {
            var reference = SearchDirection(chars, x, y, direction);
            if (reference != null)
            {
                return reference;
            }
        }
        return null;
    }

    private Coordinate SearchDirection(char[] chars, int x, int y, int direction)
    {
        // have we ve moved passed the boundary of the puzzle
        if (x < 0 || y < 0 || x >= Puzzle.GetLength(1) || y >= Puzzle.GetLength(0))
            return null;

        if (Puzzle[y, x] != chars[0])
            return null;

        // when we reach the last character in the word
        // the values of x,y represent location in the
        // puzzle where the word stops
        if (chars.Length == 1)
            return new Coordinate(x, y);

        // test the next character in the current direction
        char[] copy = new char[chars.Length - 1];
        Array.Copy(chars, 1, copy, 0, chars.Length - 1);
        return SearchDirection(copy, x + directions[direction].X, y + directions[direction].Y, direction);
    }
}

Answer 1

Keep first letters of each word your looking for in a list or some such data structure. Search every letter in order. If it is the first letter of a word you're searching for, then search every letter around it for a second letter. If you find a second letter in a word then note the direction in a word object that has a direction enum, i.e. {N = 0, NE, E, SE, S, SW, W, NW}. Then simply follow that direction until you have determined the word isn't found or is found. They key is for the search object to know how many words it's looking at. So if you're looking for both cater and cattle, if you find C-A-T going northeast, it could be either. Also, if you find an F you will need to make sure to check every direction because you can have FRIAR going east and FAT going west. Then it's as simple as making sure you don't go out of bounds because NE is X+1 Y-1, etc...

Answer 2

This is the typical problem where you should use the trie data structure: http://en.wikipedia.org/wiki/Trie

Once you have a dictionary with all the target words you go through each position of your two dimension array and call a recursive function that expands all 8 ways. Something along the lines of.

void Explore(TwoDimArray puzzle, Point2D currentCell, string currentMatch, List<string> foundSolutions);

You stop recursiveness if:
- You find a match.
- The currentMatch + currentCell's character no longer constitute a possible match.
- The currentCell position is no longer inside the puzzle area.

Answer 3

Do NOT use a 2 dimensional array for the puzzle. For an NxM word search, use an array of (N+2)*(M+2). Put padding of 1 character all the way around your puzzle. So the example becomes:

......
.BXXD.
.AXEX.
.TRXX.
.FXXX.
......

Where the periods are the padding and all of this is really a 1d array.

Calling the width of the new grid the row span (S), you can now create an array of 8 direction "vectors" D=[ -S-1, -S, -S+1, -1, 1, S-1, S, S+1 ]. Using this, you can look from any position in the grid Puzzle[position] to its neighbor in any direction by using Puzzle[position+D[direction]].

Your position of course is now a single variable instead of a pair of coordinates. The padding around the border tells you if you've reached the edge of the board and should be a character that is never used in the interior of the puzzle.

Answer 4

THIS SOLUTION IS WRITTEN IN C++ BUT THE PRINCIPLE IS THE SAME

If your puzzle is represented by

char puzzle[N][N]

declare the arrays

int xd[8] = { -1, -1,  0, +1, +1, +1,  0, -1 };
int yd[8] = {  0, -1, -1, -1,  0, +1, +1, +1 };

and then when you want to check if word 'w' can be found at location (x, y) in direction d (d between 0 and 7 inclusive), just do

bool wordsearch(const char *w, int x, int y, int d) {
  if (*w == 0) return true; // end of word
  if (x<0||y<0||x>=N||y>=N) return false; // out of bounds
  if (puzzle[y][x] != w[0]) return false; // wrong character
  // otherwise scan forwards
  return wordsearch(w + 1, x + xd[d], y + yd[d], d); 
}

And then the drivers

bool wordsearch(const char *w, int x, int y) {
  int d;
  for (d=0;d<8;d++)
    if (wordsearch(w, x, y, d)) return true;
  return false;
}

bool wordsearch(const char *w) {
  int x, y;
  for (x=0;x<N;x++) for(y=0;y<N;y++) if (wordsearch(w, x, y)) return true;
  return false;
}