How to search for a two-dimensional array in any direction

Question

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

Basic searches from left to right, top to bottom, etc. not difficult to write, but when you search diagonally across an array, everything becomes a little detailed. It works for me, but I'm sure there is a better solution there.

Here is an example puzzle that I am 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 ​​finding compass points

EDIT: The search result should return the x1, y1 and x2, y2 coordinates of the words inside the array.

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

This is the end result that I came up with. I based it on the algorithm in Antti's answer, modifying it to return the array offsets for the beginning and end of any words found. This algorithm will be used in the Word search game that I write in WPF for my children. Thanks to everyone for helping me. I will post the link here in the application when it is 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 DECISION IS WRITTEN IN C ++, BUT THE PRINCIPLE HAS THE SAME

If your puzzle is presented

 char puzzle[N][N] 

declare 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 the word "w" can be found in the location (x, y) in the d direction (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 a typical problem in which you should use the trie data structure: http://en.wikipedia.org/wiki/Trie

Once you have a dictionary with all the target words, you look at each position of your two dimensional arrays and call a recursive function that extends all 8 ways. Something like lines.

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

You stop recursion if:
- You will find the match.
- The current character currentMatch + currentCell is no longer a possible match.
- The currentCell position is no longer inside the puzzle area.

Answer 3

Keep the first letters of each word you are looking for in a list or some such data structure. Search each letter in order. If this is the first letter of the word you are looking for, then find each letter around it for the second letter. If you find the second letter in a word, then pay attention to the direction in the word object that has the renaming of the direction, i.e. {N = 0, NE, E, SE, S, SW, W, NW}. Then simply follow this direction until you determine that the word is not found or not found. They are intended for the search object to know how many words it is looking at. Therefore, if you are looking for both refreshments and cattle, if you find CAT in the northeast, it can be both. In addition, if you find F, you should definitely check all directions, because you can have a FRIEND going east and FAT going west. Then it is as simple as making sure that you do not go beyond, because NE is X + 1 Y-1, etc.

Answer 4

 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 5

DO NOT use a 2-dimensional array for the puzzle. To search for NxM words, use the array (N + 2) * (M + 2). Overlay 1 character around your puzzle. So, an example would look like this:

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

If periods are indented and all this is really a 1d array.

By calling the width of the new grid, the range of lines (S), now you can create an array of 8 directions "vectors" D = [-S-1, -S, -S + 1, -1, 1, S-1, S, S + 1]. Using this, you can look from any position in the Puzzle [position] grid to a neighboring one in any direction using Puzzle [position + D [direction]].

Your course position is now a single variable instead of a pair of coordinates. A pad around the border tells you whether you have reached the edge of the board and should be a character who is never used in the interior of the puzzle.