Longest word from array of letters

For a side project, I have to make a function search through a list of all words (80k or more).

I have an array of letters arranged like this:
abcd
efgh
ijkl
mnop

The user can go from "a" to its neighbours "b" "e" or "f". Crossing is allowed (eg. "b" to "e" to "a" and to "f").

My logic: Get all possible combinations of 3+ letters up to 16, then match every combination to the word list and remove anything that isnt a word, then sort by length.

But I dont even know where to begin!

I could hard-code all possible moves between letters, but that would be a LOT of combinations and time.

Anyone have any ideas?

I don't really understand the problem, care to elaborate a bit more on that? In theory it sounds like you want to build a trie out of your word dictionary and then check all permutations of your input against that trie.

brute-force?

use a 2d-array, write some lines of code which check every possible direction (shouldn't be too hard if it's a recursive function) and iterate through the whole array.

I need to get all possible combinations out of those letters, so I can compare them to the word list and display the real words to the user. But, its not like cracking a password, where you may have all symbols at any space, here you got adjacent nodes wich you have to connect, so the resulting combinations are limited.

I have no idea how to make a function to get all possible combinations between the letters. I dont want to hard-code the possible combinations so I can compare the resulting letters to the word list.

I cant even explain it well
I just saw its called Boggle solver in google.



*EDIT*

OK. You got me thinking
I can define the rules - from wich node you can go to wich node , and 16 temp variables to check if a node has been 'visited'...And generate all possible 'paths' for each node to every other,right?

Aha!
Now we are talking. And while we are talking, you probably don't want to brute force this, it's going to be slow as hell!

Again, put your word dictionary into a trie! Tries are perfect to match prefixes, which is exactly what you want to do. Next up create a list of all prefixes and their end positions, ie, at the beginning you have an n x n sized list one for each letter (and the matched prefix then becomes a letter). Each of these triplets looks something like this: (x, y, s) where x and y are the coordinates in the letter matrix and s is the already found prefix.

Now, go over every in the list and for each entry go over all adjacent letters (l) in the letter matrix and check s + l against the trie.
if s + l is a word, add it to the found word list
if s + l is a prefix to a word, add a new entry to the list with x and y being the position of l in the letter matrix and s being s + l

Rinse and repeat until you are done.

The rest is just iterating over the output to find the longest match, and tada you are done.
I would like to add that this idea isn't mine but comes from this StackOverflow question, which also contains some more possible solutions. You'll see a lot of tries there, which is due to the fact that tries are the perfect data structure for this sort of thing. Know your data structures

I do hope my GF will reward me for all this tonight

I know answers to this already exist in all sorts of languages and methods, but there arent any in Bulgarian alphabet

Thanks, gonna look up all this info now and try to imagine the whole thing before jumping in.