4x4 Word Grid - Java

Question

How would you go about searching if a word exist in a 4x4 Grid of random letters(A-Z).Can someone lead me into the right direction of an effective way of tackling this problem.

Here are the conditions:

• Words are formed from adjoining letter
• words can be formed horizontally, vertically or diagonally to the left, right or up-and-down
• No letter cell may be used more than once within a single word.

Thanks for your help guys!

Answer 1

If you are just working on a 4X4 grid, it should be quite simple. Scan for the first letter of the word and in every direction search if that word can be completed from the grid.

If the grid is very large and/or you are performing lots of searches you might want to pre-process the grid first. Eg. For every couple of characters (lets call them k-grams since in general you want to keep track of k characters) you can keep list of locations where they are located. When you are searching, first look for the location of k-grams of that word.

Answer 2

I would start with a representation of a grid that had both letters and blank spaces.

I would write a routine that took, as parameters, a grid like that and a starting letter, and returned a list of possible words.

I would write an iterator that returned, for such a grid, each letter adjoining a given letter. It would recognize blank spaces and not return for them.

And I would write a routine that took a letter and my grid, removed the letter from the grid, and for each letter adjoining, called itself with the new grid and the new letter.

If you really want to search for one word, you can pass it into these routines so you can fail as soon as you have a non-match.

Otherwise you can use this to generate a complete list of words.

Answer 3

You can treat this as a graph problem. Convert your grid to a graph, where each vertex represents a cell in the grid, and the edges between vertices represent valid movements between these cells.

From there, you can use the following recursive algorithm to determine if a word S can be found in the graph G:

FindWord(G, S):
1. Set C to the first letter of S.
2. Set S' to S with the first letter removed.
3. For all vertices V in G:
  3.1. If the letter in V is not C, continue to the next vertex.
  3.2. If CheckPaths(G, S', V, {}) returns true, return true.
4. Return false.

CheckPaths(G, S, V, Visited):
1. If S is empty, return true.
2. Set C to the first letter of S.
3. Set S' to S with the first letter removed.
4. Set Visited' to Visited ∪ {V}.
5. For all cells V' connected to V:
  5.1. If V' ∈ Visited, continue to the next vertex.
  5.2. If the letter in V' is not C, continue to the next vertex.
  5.3. If CheckPaths(G, S', V', Visited') returns true, return true.
6. Return false.

The actual implementation will likely be a bit different (for example, it might be a good idea to not make a copy of Visited, but share a single set by removing vertices after determining a path failed), but this is the basic idea of how to do it.