To: wordgame-programmers@yahoogroups.com From: Mark Congdon Date: Sun, 15 Sep 2002 20:45:58 -0700 (PDT) Subject: [wgp] new Boggle/Tangleword player/solver for Windows Hi...

I'm new to this board, so let me introduce myself.  My
name is Mark, and I'm a network administrator/web
designer.  I also do some programming, and have been
programming (mainly in variations of BASIC) as a hobby
since my first VIC-20.

I have also enjoyed playing Boggle for many years.  A
few years back I was staying with my sister, who is
much farther along the vocabulary spectrum than I am,
and we spent most of our time playing Boggle.  When I
left, she was bemoaning the fact that she wouldn't be
able to play against any real opponents any more (she
played a lot of solitaire).

So, I came up with a DOS-based Boggle solver, written
in C.  I developed a completely proprietary,
optimized-for-Boggle dictionary compression method,
and used the ENABLE dictionary so it would be a worthy
opponent for her.

In the last few weeks, I've gotten motivated and
rewritten the program in Windows, and added lots of
gameplay features and stuff.

I would love to discuss my dictionary/lexicon
compression scheme, and see if there are ways I could
improve on it.  I would also like to post my game on
the board's website (that's how I found the board), if
that would be appropriate.

Thanks!

Mark
To: wordgame-programmers@yahoogroups.com From: Mark Congdon Date: Mon, 16 Sep 2002 15:12:15 -0700 (PDT) Subject: [wgp] Boggle dictionary algorithm Hi again...

Here's the compression/searching method I used for my
Boggle solver program.  I'd be very interested to hear
about other ways that people have approached this, or
ways that my idea could be improved.

My main idea was to set up my dictionary/wordlist file
as a tree.  This way I could progress through the
dictionary in very much the same way my recursive
logic would be progressing through the Boggle board.

I set up my dictionary file as a series of sets of 26
4-byte numbers.  The first set of 26 numbers stands
for the 26 letters of the alphabet used as the first
letter of a word.  Each four-byte number is a pointer
to another table, for the second letter of a word that
has that first letter, and so on.  If there are no
possible words with that combination of letters (say,
XX as the first two letters of the word), the
four-byte number at that location will be zero, cuing
my program to stop searching along that recursive
path.

Where a word ends, I set the right-most bit of that
four-byte value to 1 as an "end-of-word" flag.  Then,
obviously, I strip off that bit before using the
4-byte value to redirect to the next table.

This made for a relatively fast search, but initially
generating the dictionary file was slow, and the
dictionary file itself was huge.  So, I came up with a
way of compressing the dictionary file, that slows
down the searching slightly, but saves lots of space.

In the compressed version, I first generate the entire
dictionary file in its expanded form.  Then, for each
table of 26 4-byte values, I instead write a single
4-byte value that is a "bit" table of 1's or 0's
stating whether that entry has a value associated with
it.  Then, immediately after that "bit table", I write
a 4-byte value for each "1" in the bit table.  This
saves a huge amount of space, because it removes all
the wasted space at the end of the file (when I was
writing 26*4 bytes just to add an 's' to the end of a
long word, I now only need to write 8 bytes).

This approach made it quite tricky to dynamically add
words to the dictionary, but I did find a way to work
around that (using the right-most bit of the "bit
table as a "redirector" bit).  Still, initially
generating the dictionary file is very slow, and I
can't help thinking there should be a more elegant way
to do something like this.

I'd love any feedback anyone wants to offer.  Thanks!

Mark
Date: Mon, 16 Sep 2002 16:36:52 -0700 (PDT) From: Mark Congdon Subject: Re: [wgp] new Boggle/Tangleword player/solver for Windows To: root Thanks for being willing to post my program! I'm calling it "WordCube Challenge and Solver". If you want any sort of description or tagline or anything, let me know, and I can provide one. I'm uploading the Setup file now. I already uploaded the primary source code program (WORDCUBE.BAS). There are some other supporting programs (include file, icons, etc.) that I didn't include, because they're not interesting from a research/algorithm standpoint. The program is written in Rapid-Q, a freeware compiled GUI version of BASIC. If anyone's interested, the compiler and documentation can be downloaded from http://www.basicguru.com/rapidq. The WCCSETUP.EXE file is a full install/uninstall program, that includes three complete dictionaries. The main one is a compiled version of the ENABLE2K dictionary, but it also contains modified versions of the SCOWL and 12DICTS lists, for various difficulty levels. This makes it a relatively large download. If you need a smaller version, let me know, and I can scale it down. Thanks! Mark