How do I search a two dimensional array in any direction

algorithm, c#

Solution

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

Problem

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

Original source