CODEWITHSUNDEEP
algorithm
kylex
kylex

Reputation: 14406

Word search algorithm

I am trying to come up with a better approach than the "brute force" method, but am at somewhat of a loss.

Here is a simple case:

Given a finite number of pre-chosen letters, and a hatch (like a crossword overlap) I am attempting to find all combination of words that can be used. (Words are retrieved from a dictionary database.)

Example:

Given the letters:
a,c,r,e,t,u,p,l,m,o
how many combinations of words can fit in the following crossword puzzle?

   _
 _ _ _ _ 
   _
   _
   _ _ _

One example:

  c
t r e e
  e
  e
  p o t

Of course the search time increases dramatically with each letter or addition to the crossword hatch. Any suggestions for a better way to search?

Upvotes: 11

Views: 2460

Answers (1)

Martin DeMello
Martin DeMello

Reputation: 12336

Check out the open source arccc, which fills in crossword grids by treating them as a constraint satisfaction problem. If you would like to do this yourself as a learning exercise, reading up on CSPs should be a good starting point.

As for limiting the alphabet, that's best done as a preprocessing step on the source dictionary.

Upvotes: 4

Related Questions