Finding real words in Boggle

I am thinking of making a Boggle type of game. How would I determine what combination of letters is a real word? How would I use the spell checker in MSWord, or is there a better way (preferably with out my own database)?
I would like to aviod MSWord, as it's not on all computers.

And I was wondering if there was an efficiant way of checking all those letter combinations. Every way I think of quickly becomes a tangled mess.

Any ideas would be great!
Gilmesh

you're looking at a hash table. this allows instant searches by using the letters of the word to calculate an index(key) into an array. this is an (N)0 algorithm, meaning that it takes a constant amount of time to search, regardless of the number of items in the table. I would implement this by using the index as a record number in a binary access file. you could also prescreen words using common spelling rules.

A hash table is certainly a good solution. It has the advantage of simplicity, as long as there are no colliisions (a collision is when you have 2 different words that evaluate to the same hash index). You can minimize collisions by carefully choosing your hash function, and by allocating maybe 4x as much space as you have words. ie. if you have 10,000 words, make a hash table with 40,000 elements.

You could also try a binary search. Imaging you have an array of valid words in alphabetical order. You could quite quickly search this array with a binary method:

1) pick a word from the middle of the array
2) compare with your test word
3) if equal, exit function (FOUND)
4) if the word is smaller, discard the top half of the array and look in the bottom
5) if the word is larger, discard the lower half to the array and look in upper
6) if array is too small, then exit function (NOTFOUND)
7) go to 1

The binary search is fast because it discards half of the possibilities on every pass through the loop. So if you had 10,000 words, it would take at most 12 passes. It does require that you sort the array first though, preferably with the same comparison function that you will later use to search it.





"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Hey thanks!
I have no idea what most of this means, but I'm going to research it.
What would a binary search look like?

Gilmesh

Here is an example of a binary search. It uses a global array of SORTED words. The words have been sorted alphabetically using the StrComp function....

<PRE>
Option Explicit

Dim arrWords() As String

Function FindWord(ByVal s As String) As Long
'looks for word s in array arrWords using binary search
'returns index of word, or 0 if not found
'Note that arrWords should have a lower bound of 1, not 0.
Dim lngLow&, lngHigh&, lngMid& 'pointers to positions in the array
Dim i%

lngLow = LBound(arrWords)
lngHigh = UBound(arrWords)

FindWord = 0
Do While lngHigh >= lngLow
lngMid = (lngHigh + lngLow) \ 2
i = StrComp(s, arrWords(lngMid), vbTextCompare)
Select Case i
Case -1 's < arrword
lngHigh = lngMid - 1
Case 1 's > arrword
lngLow = lngMid + 1
Case 0 'Success!
FindWord = lngMid
Exit Do
End Select
Loop

End Function

Private Sub Command1_Click()
Debug.Print FindWord(CStr(Text1))
End Sub

Private Sub Form_Load()
ReDim arrWords(1 To 10)
arrWords(1) = "alpha"
arrWords(2) = "bravo"
arrWords(3) = "Charlie"
arrWords(4) = "Delta"
arrWords(5) = "echo"
arrWords(6) = "foxtrot"
arrWords(7) = "golf"
arrWords(8) = "hotel"
arrWords(9) = "india"
arrWords(10) = "Juliet"
End Sub


</PRE>

"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder