How to find words on a hex grid

Question

I am trying to make a hex grid based word game. Currently the words are placed from a list of pre-defined words(a list of animals in this case). All colored cells make a word that was placed, while white cells are just random letter. As each word is placed, the word and the indexes needed to make that word are saved to a list for AI to use.

now:

• It is possible to make the words CAT and DOG (marked in red), other words my be possible as grid is randomly generated.
• A Human player can make these words, no problem there
• how do i add those words and their indexes to a list of words that can be made

Answer 1

I once wrote a word finder that worked with a precomputed list. Basically each letter knows which next letter is valid. You can exit the search if there is no valid letter anymore. A flag indicated that it was a whole word.

Example word list:

• Bee
• Bear
• Bees
• Bat

The only start letter with this list would be a B. If you found a B in your grid, you would check around that B if you can find either an a or an e. If you found an a, you would look around again if there is a t. No t means no valid animal. If instead of the a you found the e, you would continue to look again now for either again a or e.

Answer 2

You can do this with a series of depth-first searches, starting from each cell.

Your starting cell's letter forms the initial word prefix. In each iteration, you check if some word in your dictionary either wholly matches the current prefix (if so, add the word and the indexes you traversed to get here to the possible answer set) or if no word in your dictionary starts with this prefix (if so, abort this search branch, backtracking to the next shorter prefix).

Then you examine the neighbours of the current cell, and if any have not already been crossed in the path you took to get here, recurse on them, adding their index to your path-so-far and their letter to the end of your prefix.

If you sort your dictionary in lexicographical order, then all words matching a particular prefix will correspond to a contiguous range of indices in that list, which you can represent with a start/end index or start and count. Then you only ever have to search smaller and smaller ranges of your list, not the whole thing.

Or if you want to get fancy, you could implement your dictionary as a Finite State Acceptor that accepts only valid words, or a Transducer that maps valid words to their corresponding string or id, or a trie similarly. Then your search is effectively a constrained walk of the state graph of this data structure.