6

I'm coding a game similar to Boggle where the gamer should find words inside a big string made of random letters.

For example, there are five arrays with strings inside like this. Five rows, made of six letters each one :

AMSDNS
MASDOM
ASDAAS
DSMMMS
OAKSDO

So, the users of the game should make words using the letters available with the following restrictions and rules in mind:

  • Its not possible to repeat the same letter to make a word. Im talking about the "physical" letter, in the game that is a dice. Its not possible to use the same dice twice or more to make the word.
  • Its not possible to "jump" any letter to make a word. The letters that make the word must be contiguous.
  • The user is able to move in any direction she wants without any restriction further than the two mentioned above. So its possible to go to the top, then bottom, then to the right, then top again, and so on. So the movements to look for words might be somehow erratic.

I want to know how to go through all the strings to make words. To know the words Im gonna use a txt file with words.

I don't know how to design an algorithm that is able to perform the search, specially thinking about the erratic movements that are needed to find the words and respecting the restrictions, too.

I already implemented the UX, the logic to throw the dice and fill the boardgame, and all the logic for the six-letters dice.

But this part its not easy, and I would like to read your suggestions to this interesting challenge.

Im using Python for this game because is the language I use to code and the language that I like the most. But an explanation or suggestion of an algorithm itself, should be nice too, independently of the language.

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Juan Rodríguez Monti
  • 61
  • 1
  • 4
  • 1
    @WinnieTong (1) It has nothing to do with cstheory. (2) It is perfectly fine to ask algorithmic questions in SO. Questions don't have to be "How to split a string", a question that deals with aspects of algorithms (that can be programmed in any languages after understood) is perfectly fine. That said, I believe it is a dupe, I think I recall a similar question, looking for it. – amit Jan 07 '13 at 07:53
  • 1
    OK, it is not a dupe but a similar question (the restrictions are a bit different in the questions): [Printing all possible words from a 2D array of characters](http://stackoverflow.com/q/13680440/572670) – amit Jan 07 '13 at 07:59
  • One more thing: You should elaborate how is the dictionary of words given to you, and if you are allowed to pre-process it. Also, what is its expected size (and the size of the puzzle) – amit Jan 07 '13 at 08:01
  • Could you mean [Boggle](http://en.wikipedia.org/wiki/Boggle) rather than Boogle? – Alex L Jan 07 '13 at 08:04
  • @amit the size of the puzzle is written: every row is made of six dice, and there are five rows. To simplify the question, I used five strings. Its more complex, because every dice has 6 letters, but for the sake of what I want to know, is ok if there are five arrays filled with strings. Then, its possible to pre-process the dictionary. Finally, the dictionary is a textfile made with aspell, with all the words there, plain textfile, but Im able to modify it if its needed. – Juan Rodríguez Monti Jan 07 '13 at 08:05
  • @AlexL yes, sorry for the mistake. Fixed!. – Juan Rodríguez Monti Jan 07 '13 at 08:06

2 Answers2

4

The basic algorithm is simple.

  • For each tile, do the following.
    • Start with an empty candidate word, then visit the current tile.
    • Visit a tile by following these steps.
      • Add the tile's position's letter to the candidate word.
      • Is the candidate word a known word? If so, add it to the found word list.
      • Is the candidate word a prefix to any known word?
        • If so, for each adjacent tile that has not been visited to form the candidate word, visit it (i.e., recurse).
        • If not, backtrack (stop considering new tiles for this candidate word).

To make things run smoothly when asking the question "is this word a prefix of any word in my dictionary", consider representing your dictionary as a trie. Tries offer fast lookup times for both words and prefixes.

cheeken
  • 33,663
  • 4
  • 35
  • 42
4

You might find a Trie useful - put all dictionary words into a Trie, then make another Trie from the Boggle grid, only as long you're matching the dictionary Trie.

I.e. Dictionary trie:

S->T->A->C->K = stack
      \->R->K = stark
         \->T = start

Grid: (simplified)

STARKX 
XXXTXX 
XXXXXX

Grid trie: (only shown starting at S - also start at A for ART, etc)

S->X (no matches in dict Trie, so it stops) 
\->T->X
   \->A-R->K (match)
      | |->T (match)
      | \->X  
      \->C->K (match)
         \->X

You could visualise your Tries with GraphViz like this.

Alex L
  • 8,748
  • 5
  • 49
  • 75