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

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;
}

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.