2

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!

cclerv
  • 2,921
  • 8
  • 35
  • 43
  • As in a standard word search puzzle (straight line from start to end letter), or finding a path which worms its way through the grid and spells the word? – Michael Madsen Jan 27 '12 at 23:12
  • 4
    First figure out the logic of the problem on paper since this logic problem has nothing to do with programming and just requires some effort, sitzfleisch as my mom called it. Then work on the code. Come on back with your code if you get any errors. – Hovercraft Full Of Eels Jan 27 '12 at 23:16
  • It would be finding a path which worms its way through the grid until its spells the word. – cclerv Jan 27 '12 at 23:18
  • Search "Boggle" solving algorithms or try writing some code on your own. – xikkub Jan 27 '12 at 23:50
  • This is a duplicate of this very popular question: http://stackoverflow.com/questions/746082/how-to-find-list-of-possible-words-from-a-letter-matrix-boggle-solver – Dan J Aug 30 '12 at 00:24

3 Answers3

2

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.

Michael Madsen
  • 54,231
  • 8
  • 72
  • 83
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.

ElKamina
  • 7,747
  • 28
  • 43
  • @ruakh There are 6 words on a 4 length array. 6*2*4*2 = 96. 2 for each direction, 4 for each column and 2 again because vertical/horizontal. For diagonal it is (1+3+6+3+1)*2 = 28. 96+28=how much? – ElKamina Jan 28 '12 at 00:15
  • @ruakh In that case I take back part of my answer. Still, rest of my answer still stands. – ElKamina Jan 28 '12 at 01:17
1

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.

arcy
  • 12,845
  • 12
  • 58
  • 103