Which algorithm fits best ?

kkadir

Hello, Suppose that we have a NxN square filled with letters. Which algorithm is the best to find any words starting with NiNj and continue from the starting point through adjacent squares (left-right-cross) where the word is in any length L? Thanks and best regards..

.:: Something is Wrong ::.

PICguy

I wrote a decent 5x5 Boggle game and felt that the problem was the dictionary. So...I kept multiple partial matches going always working the partial match with the lowest lexical value. Finds game buried in some oddball directory... Discovers it does not work in xp. Posting an old result... A L E R E O O T S T T G L U T N Z O Y E S C E N F alert alertest alertly ales aloe alter alto alts colog cols colt colter coly cone coney cony coulter couter cozen cozey enfetter enol erst ester eyen eyne fets fetter fetus feus fytte glue gluey glut gluten goal goer goes gone gout gouty lest lets logo loot looter lots lotus lust luster lustre lusty lute nets nett netter neuter nolo nous oleo oles oots ousel oust ouster outer outgo outgoes outre outs outsert outset oyez reset rest result retool rets retuse scene scone scouse scout scouter sere sloe slog slot slue slut stela steno stere stereo stey stoa stole stool strette stutter stye suet suety sutler tela terse test tester testy toes tola tole tolu toluene tool tooler toot tooter tootle tootler tote toter tots trestle tret tuts tutty tyne ulster user utter yett youse zone

kkadir

So ? :confused:

.:: Something is Wrong ::.

Russell

pashje wrote:

Which algorithm is the best

It depends on the value of N and on the lenght of the dictionary (L)... If N is too big (compared with L) the best way is to try to search every word of the dictionary on the NxN square. Elseway (N small) try to extract every possible words, and then test if the word exist. BTW I prefere in both cases to use the first method. It seemes easyer to be implemented.:-D

Russell

kkadir

Well both methods will do the job surely but what if N is a Z+ ? It may 3 but also 3000.. So the performance is an important issue.. Maybe a genetic algorithm or somemthing with trees will work well ? Any text about thiss issue will really help !;)

.:: Something is Wrong ::.

Russell

if N can change from 3 to 3000...well...I think that it is not possible to find an algorithm with always an High performance. You need to implement at least 2 algorithms: the program will use the first one if NK. The treshold K must be set during your test to find what algorythm is faster. About genetic algorithms I think that this isn't the right way. I think that you can perform a tree algorithm sorting the dictionary somehow to avoid to check every words.

Russell

mulletcheese

I did my final year project on a scrabble game and i found that the best way to increase speed when matching words is by choosing an efficient data storage technique for your dictionary. A tree structure is needed to solve this problem, a DAWG would probably be the best choice.